Algorithms in a Nutshell

Binary Search

Binary Search ( Figure 5-2) delivers better performance than Sequential Search by sorting the elements in the collection in advance of the query. Binary Search divides the sorted collection in half until the sought-for item is found, or until it is determined that the item cannot be present in the smaller collection.

Figure 5-2. Binary Search fact sheet

Assume you have the telephone book for New York City and you need to find the phone number for "David Mamet." If you use Sequential Search as your algorithm, you might spend the better part of an afternoon trying to find the phone number; worse, you would have to read every entry in the phone book before determining whether the number is unlisted. Clearly, such an approach fails to take advantage of the ordered arrangement of names in the phone book. As an alternative, you would likely open the phone book to a page about halfway and see whether "David Mamet" is on that page. If the entry for "David Mamet" is on that page, then you are done; if not, and "Mamet" comes earlier in the alphabet than any last name on the page, you need only search through the first half of the phone book. Otherwise, you need to search through the back half of the phone book. This process is a "divide and conquer" strategy that rapidly locates the desired target. Note that if you get to a page on which "Mamet" should appear (if it were a listed ...