Section 9.6. Array Algorithms: Searching
9.6. Array Algorithms: SearchingSuppose 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. 9.6.1. Sequential SearchThis 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: 1. For each element of the array 2. If the element equals the key 3. Return its index 4. If the key is not found in the array 5. Return -1 (to indicate failure) 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 implementation of the sequentialSearch() method. The method takes two parameters: 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. The last statement in the method will only be reached if no element matching the key is found. Figure 9.15. The Search class. |
public class Search { public int sequentialSearch(int arr[], int key) { for (int k = 0; k < arr.length; k++) if (arr[k] == key) return k; return -1; // Failure if this is reached } // sequentialSearch() public int binarySearch(int arr[], int key) { int low = 0; // Initialize bounds int high = arr.length - 1; while (low <= high) { // While not done int mid = (low + high) / 2; if (arr[mid] == key) return mid; // Success else if (arr[mid] < key) low = mid + 1; // Search top half else high = mid - 1; // Search bottom half } // while return -1; // Post: if low > high search failed } // binarySearch() } // Search class |
Effective Design: Sentinel Return Value
 | Like Java's indexOf() method, the sequentialSearch() returns a sentinel value (-1) to indicate that the key was not found. This is a common design for search methods. |
9.6.2. 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 use of the knowledge that the array is ordered and perform a binary searcha divide-and-conquer algorithm that divides the array in half on each iteration and limits its search to just the half that could contain the key.
To illustrate a 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 log2N 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 (27 = 128 > 100). For a list of 1,000 items, a binary search would take at most 10 guesses (210 = 1,024 > 1,000).
How many guesses?
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:
TO SEARCH AN ARRAY OF N ELEMENTS IN ASCENDING ORDER 1. Assign 0 low and assign N-1 to high initially 2. As long as low is not greater than high 3. Assign (low + high) / 2 to mid 4. If the element at mid equals the key 5. then return its index 6. Else if the element at mid is less than the key 7. then assign mid + 1 to low 8. Else assign mid - 1 to high 9. If this is reached return -1 to indicate failure
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 the portion of the array 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 every location in the array to determine that the key is not in the array. It searches only the part of the array that could contain the key. For example, suppose we are searching for -5 in the following array:
int sortArr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 }; The -5 is smaller than the smallest array element. Therefore, the algorithm will repeatedly divide the low end of the array in half until the condition low > high becomes true. We can see this by tracing the values that low, mid, and high will take during the search:
Key Iteration Low High Mid ---------------------------------- -5 0 0 19 9 -5 1 0 8 4 -5 2 0 3 1 -5 3 0 0 0 -5 4 0 -1 Failure
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 performs both a sequentialSearch() and a binarySearch() for the number.
Figure 9.17. The TestSearch class.
Figure 9.18. The TestSearch class.
import java.io.*; public class TestSearch { public static int getInput() { KeyboardReader kb = new KeyboardReader(); kb.prompt("This program searches for values in an array."); kb.prompt( "Input any positive integer (or any negative to quit) : "); return kb.getKeyboardInteger(); } // getInput() public static void main(String args[]) throws IOException { int intArr[] = { 2,4,6,8,10,12,14,16,18,20,22,24,26,28}; Search searcher = new Search(); int key = 0, keyAt = 0; key = getInput(); while (key >= 0) { keyAt = searcher.sequentialSearch( intArr, key ); if (keyAt != -1) System.out.println(" Sequential: " + key + " is at intArr[" + keyAt + "]"); else System.out.println(" Sequential: " + key + " is not contained in intArr[]"); keyAt = searcher.binarySearch(intArr, key); if (keyAt != -1) System.out.println(" Binary: " + key + " is at intArr[" + keyAt + "]"); else System.out.println(" Binary: " + key + " is not contained in intArr[]"); key = getInput(); } // while } // main() } // TestSearch class |
Self-Study Exercise
| Exercise 9.13 | For an 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. |
EAN: 2147483647
Pages: 275