Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 773

Binary Search
Sometimes you'll want to search through elements of an array or list that you know is
in sorted order. For example, if you wanted to know whether “queasy” was a real
English word, you could search the contents of an alphabetized dictionary text file.
Likewise, you might find yourself looking for a book written by Robert Louis
Stevenson in a list of books sorted by the author's last name. If the dictionary is large
or the list of books is long, you probably won't want to sequentially examine all the
items it contains.
There's a better algorithm called binary search that searches sorted data much
faster than a sequential search. A normal sequential search of a million-element array
may have to examine all the elements, but a binary search will need to look at only
around 20 of them. Java's class libraries contain methods that implement the binary
search algorithm for arrays and lists.
Binary Search
An algorithm that searches for a value in a sorted list by repeatedly dividing
the search space in half.
The binary search algorithm begins by examining the center element of the array
or list. If the center element is smaller than the target you're searching for, there's no
reason to examine any elements to the left of the center (at lower indexes). If the cen-
ter element is larger than the target you're searching for, there's no reason to examine
any elements to the right of the center (at greater indexes). Each pass of the algorithm
eliminates half the search space from consideration, so in most cases the algorithm
finds the target value much faster than a sequential search would have found it.
The logic of the binary search algorithm is similar to the strategy that people use
in a high/low guessing game in which the computer generates a random number
between 1 and 100 and the user tries to guess it. After each incorrect guess, the pro-
gram gives a hint about whether the user's guess was too high or too low. A poor
algorithm for this game is to guess 1, 2, 3, and so on. A smarter algorithm is to guess
the middle number and cut the range in half each time on the basis of whether the
guess was too high or too low. Figure 13.1 shows how this works.
A binary search uses this same approach when it searches a sorted array for a
target value. The algorithm scales extremely well to large input data. The Arrays
class in the java.util package contains a static method called binarySearch that
implements the binary search algorithm. It accepts an array of any suitable type and
a target value as its parameters and returns the index where you can find the target
element. If the element isn't found, the method returns a negative index.
The following code uses the Arrays.binarySearch method to find a number in
an array of integers. It needs to examine only indexes 4, 6, and then 5 in order to find
the target value at index 5: