Recursive Algorithms - Binary Search

The binary search algorithms (aka half-interval search) finds the position of an element in an sorted array by comparing the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element and comparing with the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. It runs in an O(log N) time.

Let’s take a look at the binary search algorithm and how it uses recursion to find a value in a sorted array:

• First we consider an arbitrary sorted array (not a dictionary with pages and words on pages.) The algorithm is given an array of values.
• The return value should be either the index in the array where the item is found or an indication that it is not in the array at all. Since array indices are always non-negative, we can use -1 to indicate that the search failed.
• Third is the issue of how to find the middle of the array. The middle is the index halfway between the top index and the bottom index of the part of the array being searched. Since the part of the array being searched must vary depending on the results of comparisons, the top and bottom of the search range will be parameters of the function.

Putting this together, the algorithm becomes:

int binarySearch(int [] theArray, int bottom, int top) {
  if (bottom > top) {
    // the function was called with an empty range
    return -1;
    else { // top >= bottom
      // find the middle index
      int middle = (top + bottom) / 2;
      // compare keyword to value at the middle
      if (keyword < theArray[middle])
        // keyword is not in the upper half so try again in lower half
        return binary_search(theArray, bottom, middle - 1, keyword);
      else if (keyword > theArray[middle])
        // keyword is not in the lower half so try again in upper half
        return binary_search(theArray, middle + 1, top, keyword);
      else
        // keyword >= theArray[middle] && keyword <= theArray[middle],
        // so keyword == theArray[middle] and we found it
        return middle;
    }
  }
}

Notes.

1. The comparisons are ordered so that first it checks if the keyword is less than the array element, then larger, and if both fail, it must be equal. This is more efficient than checking equality first. We’ll leave up to the readers to determine why?