@InProceedings{RMKWS78,
replaced-by = { RMKWS80 },
author = { R(onald) L. Rivest and A(lbert) R. Meyer and D(aniel) J. Kleitman
and K(arl) Winklmann
and J(oel) Spencer
},
title = { Coping with errors in binary search procedures (Preliminary report) },
pages = { 227--232 },
url = { http://doi.acm.org/10.1145/800133.804351 },
doi = { 10.1145/800133.804351 },
acmid = { 804351 },
acm = { 08259 },
booktitle = { Proceedings of the tenth annual ACM symposium on Theory of computing },
publisher = { ACM },
editor = { Richard J. Lipton },
date = { 1978 },
OPTyear = { 1978 },
OPTmonth = { May 1--3, },
eventdate = { 1978-05-01/1978-05-03 },
eventtitle = { STOC '78 },
venue = { San Diego, California },
OPTorganization = { ACM },
abstract = {
We consider the problem of identifying an unknown
value $x \in \{1,2,...,n\}$ using only comparisons of $x$
to constants when as many as $E$ of the comparisons
may receive erroneous answers. For a continuous
analogue of this problem we show that there is a
unique strategy that is optimal in the worst
case. This strategy for the continuous problem is
then shown to yield a strategy for the original
discrete problem that uses
$\log_2 n + E\cdot\log_2\log_2 n + O(E\cdot \log_2 E)$
comparisons in the worst case. This number is shown
to be optimal even if arbitrary ``Yes-No'' questions
are allowed.
\par
We show that a modified version of this
search problem with errors is equivalent to the problem
of finding the minimal root of a set of increasing
functions. The modified version is then also shown
to be of complexity
$\log_2 n + E\cdot\log_2\log_2 n + O(E\cdot\log_2 E)$.
},
}