×

Unbounded searching algorithms. (English) Zbl 0698.68060

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.

MSC:

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI