Searching with known error probability (Q1115619)

We study the problem of interactive searching in a set of numbers using comparison queries, under the assumption that each answer can be erroneous with a constant probability p and that a given reliability \(0<q<1\) of the result is required. The search is considered in three versions: continuous (the search space is the interval [0,1] and the unknown real x has to be found with a given accuracy 1/n), discrete bounded (x\(\in \{1,...,n\})\) and discrete unbounded (the unknown number n can be any positive integer). We prove that in all cases the search is feasible for any n and q iff \(p\neq\). For \(p\neq\) an O(log n) searching algorithm is given in the continuous case and \(O(\log^ 2 n)\) algorithms in the discrete bounded and unbounded cases. For \(p<1/3\) or \(p>2/3\), O(log n) algorithms are given in each version of search.