Binary Searching in the Presence of Comparison Errors

We consider the problem of identifying an unknown value X 2 fa1; : : : ; ang using only "X • C?" queries, when at most E of the comparisons may receive erroneous answers. We describe a strategy that solves this prob-lem by using a number of comparisons that is close to the optimal. In fact we show we need less than log(n) + E log(log(n)) + log(log(n) + E log(log(n)) + O(log(log(log(n))) + O(E log(E)) comparisons, while the bound for the problem is log(n) + E log(log(n)) +O(E log(E))