Java, Java, Java

Suppose we have a large array and we need to find one of its elements. We need an algorithm to search the array for a particular value, usually called the key. If the elements of the array are not arranged in any particular order, the only way we can be sure to find the key, assuming it is in the array, is to search every element, beginning at the first element, until we find it.

Sequential Search

This approach is known as a sequential search, because each element of the array will be examined in sequence until the key is found (or the end of the array is reached). A pseudocode description of this algorithm is as follows:

,,

 

 

 

J

 

SECTION 9.6 • Array Algorithms: Searching415

This algorithm can easily be implemented in a method that searches an integer array, which is passed as the method’s parameter. If the key is found in the array, its location is returned. If it is not found, then 1 is returned to indicate failure.

The Search class (Figs. 9.15 and 9.16) provides the Java implementa-

tion of the sequentialSearch() method. The method takes two pa- rameters: the array to be searched and the key to be searched for. It uses

 

a for statement to examine each element of the array, checking whether it equals the key or not. If an element that equals the key is found, the method immediately returns that element’s index. Note that the last state- ment in the method will only be reached if no element matching the key is found.

,,

Figure 9.15: The Search class.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

Figure 9.16: The Search class contains both a sequentialSearch()

and a binarySearch().

 

Binary Search

If the elements of an array have been sorted into ascending or descending order, it is not necessary to search sequentially through each element of the array in order to find the key. Instead, the search algorithm can make

 

 

 

 

 

 

 

 

 

 

 

 

How many guesses?

use of the knowledge that the array is ordered and perform what’s known as a binary search, which is a divide-and-conquer algorithm that divides the array in half on each iteration and limits its search to just that half that could contain the key.

To illustrate the binary search, recall the familiar guessing game in which you try to guess a secret number between 1 and 100, being told “too high” or “too low” or “just right” on each guess. A good first guess should be 50. If this is too high, the next guess should be 25, because if 50 is too high the number must be between 1 and 49. If 50 was too low, the next guess should be 75, and so on. After each wrong guess, a good guesser should pick the midpoint of the sublist that would contain the secret number.

Proceeding in this way, the correct number can be guessed in at most log₂N guesses, because the base-2 logarithm of N is the number of times you can divide N in half. For a list of 100 items, the search should take no more than seven guesses (2⁷ = 128 > 100). For a list of 1, 000 items, a binary search would take at most ten guesses (210 = 1, 024 > 1, 000).

So a binary search is a much more efficient way to search, provided the array’s elements are in order. Note that “order” here needn’t be numeric order. We could use binary search to look up a word in a dictionary or a name in a phone book.

A pseudocode representation of the binary search is given as follows:

,,

 

 

 

 

 

 

 

 

 

J

Just as with the sequential search algorithm, this algorithm can easily be implemented in a method that searches an integer array that is passed as the method’s parameter (Fig. 9.16). If the key is found in the array, its location is returned. If it is not found, then 1 is returned to indicate failure. The binarySearch() method takes the same type of parameters as sequentialSearch(). Its local variables, low and high, are used as pointers, or references, to the current low and high ends of the array, respectively. Note the loop-entry condition: low <= high. If low ever becomes greater than high, this indicates that key is not contained in the array. In that case, the algorithm returns 1.

As a binary search progresses, the array is repeatedly cut in half and low and high will be used to point to the low and high index values in that portion of the array that is still being searched. The local variable mid is used to point to the approximate midpoint of the unsearched portion of the array. If the key is determined to be past the midpoint, then low is adjusted to mid+1; if the key occurs before the midpoint, then high is

 

set to mid-1. The updated values of low and high limit the search to the unsearched portion of the original array.

Unlike sequential search, binary search does not have to examine ev- ery location in the array to determine that the key is not in the array. It searches only that part of the array that could contain the key. For example, suppose we are searching for −5 in the following array:

,,

 

J

The 5 is smaller than the smallest array element. Therefore, the algo- rithm will repeatedly divide the low end of the array in half until the con- dition low > high becomes true. We can see this by tracing the values that low, mid, and high will take during the search:

,,

 

 

 

 

 

 

 

As this trace shows, the algorithm examines only four locations to determine that 5 is not in the array. After checking location 0, the new value for high will become 1, which makes the condition low <= high false. So the search will terminate.

The TestSearch class (Figs. 9.17 and 9.18) provides a program that can be used to test two search methods. It creates an integer array, whose values are in ascending order. It then uses the getInput() method to input an integer from the keyboard and then performs both a sequentialSearch() and a binarySearch() for the number.

SELF-STUDY EXERCISE

EXERCISE 9.13 For the array containing the elements 2, 4, 6, and so on up to 28 in that order, draw a trace showing which elements are examined if you search for 21 using a binary search.