COPING WITH ERRORS IN BINARY SEARCH PROCEDURES.

R. L. Rivest, A. R. Meyer, D. J. Kleitman, K. Winklmann, Joel Spencer

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The problem is considered of identifying an unknown value x belonging left brace 1,2,. . . ,n right brace using only comparisons of x to constants when as many as E of the comparisons may receive erroneous answers. For a continuous analog of this problem it is shown 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//2n plus E multiplied by (times) log//2log//2n plus O(E multiplied by (times) log//2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary ″Yes-No″ questions are allowed. It is shown 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//2n plus E multiplied by (times) log//2log//2n plus O(E multiplied by (times) log//2E).

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherACM
Pages227-232
Number of pages6
StatePublished - 1978
EventConf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA
Duration: May 1 1978May 3 1978

Other

OtherConf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp
CitySan Diego, CA, USA
Period5/1/785/3/78

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'COPING WITH ERRORS IN BINARY SEARCH PROCEDURES.'. Together they form a unique fingerprint.

Cite this