The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.3.2 Searching

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A set S of n keys, a query key q.

Problem: Where is q in S?

Excerpt from The Algorithm Design Manual: We treat searching here as a problem distinct from dictionaries because simpler and more efficient solutions emerge when our primary interest is static searching. These little data structures can yield large performance improvements when properly employed in an innermost loop. Also, several of the ideas from list and array searching, such as binary search and self-organization, apply to other problems and justify our attention.

There are two basic approaches to array searching: sequential search and binary search. Both are simple, yet have interesting and subtle variations. In sequential search, we simply start from the front of our list or array of keys and compare each successive item against the key until we find a match or reach the end. In binary search, we start with a sorted array of keys. To search for key $q$, we compare $q$ to the middle key $S_{n/2}$. If $q$ is before $S_{n/2}$, it must reside in the top half of our set; if not, it must reside in the bottom half of our set. By repeating this process on the correct half, we find the key in a total of $\lceil \lg n \rceil$ comparisons. This is a big win over the $n/2$ comparisons we expect with sequential search.


Implementations

  • Standard Template library in C++ form SGI (C++) (rating 10)
  • Java Collections (Java) (rating 9)
  • Weisses Data Structure (C++,C,Java,ADA) (rating 8)
  • Handbook of Algorithms and Data Structures (C,Pascal) (rating 5)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 5)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)

  • Recommended Books

    Data Structures and Algorithm Analysis in C++ (3rd Edition) by Mark Allen Weiss Handbook of Data Structures and Applications by D. Mehta and S. Sahni The Art of Computer Programming : Sorting and Searching by Donald Knuth
    The Art of Computer Programming: Fundamental Algorithms by Donald Knuth Handbook of Algorithms and Data Structures by G. Gonnet and R. Baeza-Yates Constructive Combinatorics by D. Stanton and D. White
    The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman

    Related Problems


      
    Dictionaries
      
    Sorting



    This page last modified on 2008-07-10 .
    www.algorist.com