Algorithms in a Nutshell

(^112) | Chapter 5: Searching
Binary Search
BINARYSEARCH(Figure 5-2) delivers better performance than SEQUENTIAL
SEARCHby sorting the elements in the collection in advance of the query. BINARY
SEARCHdivides 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.
Assume you have the telephone book for New York City and you need to find the
phone number for “David Mamet.” If you use SEQUENTIALSEARCHas your algo-
rithm, 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 phone number) but it actually does not, then you know—without
looking at any other page—that Mamet’s phone number is not present in the
phone book.
Figure 5-2. Binary Search fact sheet
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use