Beigel, Richard Unbounded searching algorithms. (English) Zbl 0698.68060 SIAM J. Comput. 19, No. 3, 522-537 (1990). Summary: 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 demonstrated. Cited in 6 Documents MSC: 68P10 Searching and sorting 68Q25 Analysis of algorithms and problem complexity Keywords:table lookup; prefix code; computability; parallel algorithm; unbounded search PDFBibTeX XMLCite \textit{R. Beigel}, SIAM J. Comput. 19, No. 3, 522--537 (1990; Zbl 0698.68060) Full Text: DOI