1.1 Binary Search1 Algorithms and Data Structures in Java1 Algorithms and Data Structures in Java1.2 Simple Sorting

1.1 Binary Search

We have already seen in the previous section how to search in an array by sequentially running through the array and comparing each element with a given key. In worst case, we have to investigate the whole array to find the desired element (or find out that the element is not in the array). If the array consists of n elements, this requires n comparison operations; therefore we call the search algorithm  linear in the length of the input array.

There is a better way of searching for an element in an array provided that the array is sorted, i.e., the elements of the array are arranged in some (e.g., ascending) order. Assume that we are looking for the element 13 in the array

Binary Search

We denote the index range of the array by the variables low (initially 0) and high (initially 7) and take a look at the element in the middle referenced by the variable mid (initially 3 = (low+high)/2).
We use truncated integer division.
If this element is equal to 13, we are done. However, the element at this position is 7 which is less than 13. Since the array is sorted, we therefore know that the wanted element is to the right of mid. Thus we set the variable low to mid+1 and continue the search:

Binary Search

The process is iterated until the element is found or low > high (in this case the element is not in the array).

The following applet illustrates the algorithm.

If you don't see the applet, your Browser does not support Java. Click here, to view a precomputed image.
First press the New button; then enter the size of the array to be investigated (say 60), then press the New button three times and the Fill button three times. Now select Binary search and enter the number to be searched. Press the Find button until the algorithm has found the element or determined that it is not in the array.

Applet

The algorithm is expressed by the following Java function:

  // ------------------------------------------------
  // i = binarySearch(a, x)
  // 'i' is the index of 'x' in 'a'.
  //
  // Input:
  //   'a' is not null and sorted in ascending order.
  // Output:
  //   'a' remains unchanged.
  //   if 'i' == -1, then 'x' is not in 'a'.
  //   if 'i' != -1, then 'a[i] == x'.
  // ------------------------------------------------
  static int binarySearch(int[] a, int x)
  {
    int low = 0;
    int high = a.length-1;
    while (low <= high)
    {
      // x does not occur in a in any position
      // less than low or greater than high
      int mid = (low + high)/2;
      if (a[mid] == x) return mid;
      if (x > a[mid])
        low = mid+1;
      else
        high = mid-1;
    }
    // x does not occur in a
    return -1;
  }

Since in every iteration the size of the search range (the difference between high and low) is halved, the function needs at most as many comparisons as correspond to the binary logarithm of the length of the array; we call the algorithm  logarithmic in the array length. For instance, if the array is 1024=210 elements long, at most 10 iterations are required to find an element or determine that the element is not in the array. Sorted arrays can therefore be searched very quickly compared with arrays that are not sorted.


© Wolfgang Schreiner; February 3, 2005

1.1 Binary Search1 Algorithms and Data Structures in Java1 Algorithms and Data Structures in Java1.2 Simple Sorting