Unbounded Searching Algorithms
Richard Beigel · SIAM Journal on Computing · 1990
The unbounded search problem was posed by Bentley and Yao. It is the problem of finding a key in a linearly ordered unbounded table, with the proviso that the number of comparisons is to be minimized. It is shown that Bentley and Yao’s lower bound is essentially optimal, and some new upper bounds for the unbounded search problem are proven. The solution of this problem in parallel is demon-strated.