Sample complexity of continuous binary search with noisy information
I-Jeng Wang, Edwin K. P. Chong, Russell W. Quong · 2002
Studies the sample complexity of a continuous binary search problem with probabilistic noise present in the information. The authors derive a general lower bound on the complexity and propose an algorithm that can solve the problem with arbitrary accuracy and confidence. The authors also give the sufficient condition on the number of samples for the success of the algorithm.>