Home Java Java-tips Algorithms Searching Algorithms: Recursive Binary Search

Ask Questions?

View Latest Questions

Advertisement


 
 

Algorithms: Recursive Binary Search
Posted on: July 26, 2006 at 12:00 AM
Iterative algorithms, ie those with a loop, can usually be easily rewritten to use recursive method calls instead of loops.

Java Notes: Algorithms: Recursive Binary Search

Recursive Binary Search

Iterative algorithms, ie those with a loop, can usually be easily rewritten to use recursive method calls instead of loops. However 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 (eg, binary tree traversal). Iterative binary search is more efficient than the 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 to solve a smaller problem, ie, either the upper or lower half of the array.

Example

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
/** Recursive binary search of sorted array.    Negative value on failure.
 *  The upperbound index is not included in the search.
 *  This is to be consistent with the way Java in general expresses ranges.
 *  The performance is O(log N).
 *  @param sorted Array of sorted values to be searched.
 *  @param first Index of beginning of range.  First element is a[first].
 *  @param upto  Last element that is searched is sorted[upto-1].
 *  @param key   Value that is being looked for.
 *  @return      Returns index of the first match, or or -insertion_position 
 *               -1 if key is not in the array. This value can easily be
 *               transformed into the position to insert it.
 */
public static int rBinarySearch(int[] sorted, int first, int upto, int key) {
    
    if (first < upto) {
        int mid = (first + upto) / 2;  // Compute mid point.
        if (key < sorted[mid]) {
            return rBinarySearch(sorted, first, mid, key);
            
        } else if (key > sorted[mid]) {
            return rBinarySearch(sorted, mid+1, upto , key);
            
        } else {
            return mid;   // Found it.
        }
    }
    return -(first + 1);  // Failed to find key
}

Related Pages

Binary Search
Copyleft 2006 Fred Swartz MIT License
Advertisement


DMCA.com