# 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