@InProceedings{RMK78, replaced-by = { RMSKW80 }, author = { Ronald L. Rivest and Albert R. Meyer and Daniel J. Kleitman }, 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)$. }, }