Binary search of a sorted list is the standard method for searching for an input value in a set of numbers or for finding the element in the set which is closest to the input value. The information theory lower bound says that binary search is the fastest comparison based algorithm for these problems. Binary search is also optimal on the standard RAM model.

I will present a survey of various deterministic searching algorithms that are better than binary search. This includes a new algorithm that is optimal for general computational models. Corresponding lower bounds will also be mentioned.

Host: Joan F. Boyar