Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
range binaryRangedSearch(int array[], int searchValue, int minimumSearchBounds,int maximumSearchBounds)
{
// We would perform the search much like above
// where we go to find the value. But once we've found it,
// we need to find out where it occurs first and where it occurs last.
if (minimumSearchBounds > maximumSearchBounds) {
range notFound = {-1, 0};
return notFound;
}
// First, look at the halfway point; is it more or less than the search value?
int middleIndex = minimumSearchBounds + ((maximumSearchBounds - minimumSearchBounds) / 2);
int middleValue = array[middleIndex];
if (middleValue == searchValue) {
// We've found one instance of this
range foundRange = {middleIndex, 1};
// Now we collate the ranges above and below
range lowerRange = binaryRangedSearch(array, searchValue, minimumSearchBounds, middleIndex - 1);
range upperRange = binaryRangedSearch(array, searchValue, middleIndex + 1, maximumSearchBounds);
if (lowerRange.index != -1) {
foundRange.index = lowerRange.index;
foundRange.length += lowerRange.length;
}
foundRange.length += upperRange.length; // we don't need to check if it was not found, since the length will just be 0 then
return foundRange;
} else if (middleValue > searchValue) {
return binaryRangedSearch(array, searchValue, minimumSearchBounds, middleIndex - 1);
} else {
return binaryRangedSearch(array, searchValue, middleIndex + 1, maximumSearchBounds);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment