C++ Notes: Algorithms: Recursive Binary Search

Recursive Binary Search

Iterative algorithms, ie those with a loop, can usually be easily rewritten to use recursive function calls instead of loops. This is almost always a bad idea because the iterative version is usually simpler, faster, and uses less memory.

Some problems, eg traversing a tree, are better solved recursively because the recursive solution is so clear (see Binary Tree Traversal). Binary search is really is better in the non-recursive form, but it is one of the more plausible algorithms to use as an illustration of recursion.

This recursive version checks to see if we're at the key (in which case it can return), otherwise it calls itself so solve a smaller problem, ie, either the upper or lower half of the array.

Example

int rBinarySearch(int sortedArray[], int first, int last, int key) {
   // function:
   //   Searches sortedArray[first]..sortedArray[last] for key.  
   // returns: index of the matching element if it finds key, 
   //         otherwise  -(index where it could be inserted)-1.
   // parameters:
   //   sortedArray in  array of sorted (ascending) values.
   //   first, last in  lower and upper subscript bounds
   //   key         in  value to search for.
   // returns:
   //   index of key, or -insertion_position -1 
   //                 if key is not in the array.
   
   if (first <= last) {
       int mid = (first + last) / 2;  // compute mid point.
       if (key == sortedArray[mid]) 
           return mid;   // found it.
       else if (key < sortedArray[mid]) 
           // Call ourself for the lower part of the array
           return rBinarySearch(sortedArray, first, mid-1, key);
       else
           // Call ourself for the upper part of the array
           return rBinarySearch(sortedArray, mid+1, last, key);
   }
   return -(first + 1);    // failed to find key
}

Related Pages

Binary Search