Search for point in interval, with high–low feedback
Steve Alpern · Mathematical Proceedings of the Cambridge Philosophical Society · 1985
A point H is known to lie on a given bounded interval ℋ. A searcher wishes to locate H by making successive guesses g 1 , g 2 , … , each with the knowledge of whether the previous guesses were too high or low, or exactly right. Under these circumstances it is easy to devise a search strategy which ensures the convergence of the g i to H. One such strategy is the ‘halving’ strategy which always guesses the midpoint of the interval on which H is currently known to lie. The problem becomes well defined, and more difficult, if the searcher has to minimize a given cost function which in some way measures the speed of convergence of the g i to H.