Searching - Data Structures and Abstractions with Java - page 449

FIGURE 18-4

Coins sorted by their mint dates

1992 1995 1997 1998 2005 2009 2010 2012

If our array is sorted into either ascending or descending order, we can use the previous ideas
to revise the sequential search. This modified search can tell whether an item does not occur in an
array faster than a sequential search of an unsorted array. The latter search always examines the
entire array in this case. With a sorted array, however, the modified sequential search often makes
far fewer comparisons to make the same determination. Exercise 2 at the end of this chapter asks
you to implement a sequential search of a sorted array.
After expending the effort to sort an array, you often can search it even faster by using the
method that we discuss next.

A Binary Search of a Sorted Array
18.9

Think of a number between 1 and 1 million. When I guess at your number, tell me whether my
guess is correct, too high, or too low. At most, how many attempts will I need before I guess cor-
rectly? You should be able to answer this question by the time you reach the end of this section!
If you had to find a new friend's telephone number in a printed directory, what would you do?
Typically you would open the book to a page near its middle, glance at the entries, and quickly see
whether you were on the correct page. If you were not, you would decide whether you had to look
at earlier pages—those in the left “half ” of the topic—or later pages—those in the right “half.”
What aspect of a telephone directory enables you to make this decision? The alphabetical order of
the names does.
If you decided to look in the left half, you could ignore the entire right half. In fact, you could
tear off the right half and discard it, as Figure 18-5 illustrates. You have reduced the size of the
search problem dramatically, as you have only half of the topic left to search. You then would
repeat the process on this half. Eventually you would either find the telephone number or discover
that it is not there. This approach—called a binary search —sounds suspiciously recursive.

18.10

Let's adapt these ideas to searching an array a of n integers that are sorted into ascending order.
(Descending order would also work with a simple change in our algorithm.) We know that

a[0] ≤ a[1] ≤ a[2] ≤ . . . ≤ a[n - 1]

Because the array is sorted, we can rule out whole sections of the array that could not possibly con-
tain the number we are looking for—just as you ruled out an entire half of the telephone directory.
For example, if we are looking for the number 7 and we know that a[5] is equal to 9, then, of
course, we know that 7 is less than a[5] . But we also know that 7 cannot appear after a[5] in the
array, because the array is sorted. That is,

7 < a[5] ≤ a[6] ≤ . . . ≤ a[n-1]