Array Algorithms: Searching

Section 9.6 Array Algorithms: Searching

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.

Subsection 9.6.1 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:

Algorithm 9.6.1. Sequential search.

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 (Figure 9.6.2 and Listing 9.6.3) 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. Note that the last statement in the method will only be reached if no element matching the key is found.

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()
  
  public static void main(String[] args)
  {
     int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     Search s = new Search();
     System.out.println("Seq search for 5 at position: " + s.sequentialSearch(array, 5));
     System.out.println("Seq search for 11 at position: " + s.sequentialSearch(array, 11));
     System.out.println("Binary search for 5 at position: " + s.binarySearch(array, 5));
  }
}//Search

Listing 9.6.3. The Search class contains both a sequentialSearch() and a binarySearch().

Principle 9.6.4. 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.

Subsection 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 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_2 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^7 = 128 > 100\)). For a list of \(1,000\) items, a binary search would take at most ten guesses (2\(^{10}=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:

Algorithm 9.6.5. Binary search.

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 (Listing 9.6.3).

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\text{.}\)

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 every 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:

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

Figure 9.6.6. Binary search trace.

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\text{,}\) which makes the condition low <= high false. So the search will terminate.

The TestSearch class (Figure 9.6.7 and Listing 9.6.8) 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.

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

Listing 9.6.8. The TestSearch class.

Exercises Self-Study Exercise

1. Binary search.

Suppose we use binary search 9.6.5 to search for 21 in the following array of numbers:

0  1  2  3  4   5   6   7   8   9   10  11  12  13   subscripts
2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28   values

Which of the following shows the value of mid on each iteration of the search?

7, 11, 9, 8
Incorrect
7, 10, 8, 9
Incorrect
7, 10, 8, 9
Incorrect
6, 10, 8, 9
Correct.

Hint.

Figure 9.6.6

You have attempted of activities on this page.

Prev Top Next