Binary search of a sorted list is the standard method for determining the membership of an input value in a set of numbers or for finding its predecessor: the largest element in the set smalller than 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.
Time and Location: see main colloquium page