Skip to content

Instantly share code, notes, and snippets.

@rugbyprof
Created February 23, 2012 05:26
Show Gist options
  • Save rugbyprof/1890665 to your computer and use it in GitHub Desktop.
Save rugbyprof/1890665 to your computer and use it in GitHub Desktop.
Recursive Binary Search
//Source: http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html
int recBinarySearch(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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment