@InProceedings{RivestMeyerKleitman-1978-STOC-Coping-with-errors,
  replaced-by =  { RivestMeyerSpencerKleitmanWinklmann-1980-Coping-with-errors },
  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 },
  series = 	 { STOC '78 },
  location =     { San Diego, California },
  booktitle =    { Proceedings of the tenth annual ACM symposium on Theory of computing },
  year =         { 1978 },                  
  month = 	 { May 1--3, },
  publisher =    { ACM },
  editor = 	 { Richard J. Lipton },
  OPTcrossref =  {},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTaddress = 	 {},
  OPTorganization = { ACM },
  OPTnote = 	 {},
  OPTannote = 	 {},
  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)$.  
                   },
}