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 - first) / 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
}
|