DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

                           Searching is Not Simple                           

                                Faith E. Fich                                
                University of Toronto, Universite de Paris-Sud               

                     Tuesday, April 20, 1999, at 2:15 PM                     
                               The Seminar Room                              


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.


                                                               Joan F. Boyar