Coping with errors in binary search procedures (Preliminary Report)

ABSTRACT

We consider the problem of identifying an unknown value x&egr;{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 log2n+E.log2log2n+O(E.log2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed. 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 log2n+E.log2log2n+0(E.log2E).

REFERENCES

• 1: Berlekamp, E.R., "Block Coding for the Binary Symmetric Channel with Noiseless, Delayless Feedback," in Error-Correcting Codes (Wiley, 1968), pp. 61-85.
• 2: Brylawski, T.H., "The Mathematics of Watergate," (Unpublished paper)
• 3: Gal, S., B. Bacherlis, and A. Ben-Tal, "On Finding the Maximum Range of Validity of a Constrained System," SlAM J. Control and Opt., to appear.
• 4: Katona, G.O.H., "Combinatorial Search Problems," in A Survey of{ Combinatorial Theory (Chapter 23), (North-Holland, 1973).
• 5: Rivest,R.L., A.R. Meyer, D.J. Kleitman, and J. Spencer, "Binary Search Using Unreliable Comparisons," in Proc. 15th Annual Allerton Conf. on Communication, Control, and Computing, Sept. 28-30,1977.
• 6: Schalkwijk, J.P.M., "A Class of Simple and Optimal Strategies for Block Coding on the Binary Symmetric Channel with Noiseless Feedback," in IEEE Trans. on Information Theory 17, 3(1971), pp.283-287.
• 7: Ulam, S.M., Adventures of a Mathematician (Charles Scribner's Sons, New York, 1976), p. 281.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms