// The actual interface method which is the solution to the problem
std::pair<int, int> getRange(const std::vector<int>& numbers, int value)
{
return getRange(numbers, 0, numbers.size(), value, -1, -1);
}
As you can see, in the Function above I am just calling an overloaded version of the same function, which contains the actual algorithm implementation. I added lots of explanatory comments so no more text, just the code:
// Obviously this should be just an implementation detail
// so you don't want this be part of an interface of your
// class/lib.
// Note the currentLow and currentUp parameters, they are
// meant to keep track of the so-far-found range of
// occurrences, to pass down to the same function through
// recursive calls.
std::pair<int, int> getRange(
const std::vector<int>& numbers,
int begin,
int end,
int value,
int currentLow = -1,
int currentUp = -1)
{
// First of all, since the original array is sorted,
// we don't need to look for anything if the element
// we're looking for is less than the first
// element of the array or greater than the last,
// meaning that it's not there for sure. So just
// returning the not found value.
if (value < numbers[begin] || value > numbers[end - 1])
{
return std::make_pair(currentLow, currentUp);
}
// On the other hand, if the first and last elements
// of the array are equal to the one we're looking for,
// it means all the elements between are also equal
// because the array is sorted. Hence, we just return
// the whole range.
if (numbers[begin] == value && numbers[end - 1] == value)
{
return std::make_pair(begin, end - 1);
}
// If none of the easy cases happen, then we just
// split the array in two, and try to look for the
// range in a binary search fashion.
// If the middle element is greater than the value, then
// obviously, if the element is in the array, it's in the
// first half (left from middle), so we just call the
// function recursively with the cut range.
if (value < numbers[middle])
{
// look in first half
return getRange(
numbers,
begin,
middle,
value,
currentLow,
currentUp);
}
// Same here - but looking in the other half.
else if (value > numbers[middle])
{
// look in 2nd half
return getRange(
numbers,
middle,
end,
value,
currentLow,
currentUp);
}
// This is the most interesting case, when middle element
// is equal to the given value, it means there might be
// occurrences both on left and right sides. Now we call
// the function recursively for both left and right
// sections, but we only take the lower bound from left
// section and the upper bound from the right.
else
{
currentLow = (currentLow > middle || currentLow == -1) ?
middle : currentLow;
currentUp = (currentUp < middle) ? middle : currentUp;
// look in both
int lowerBound = getRange(
numbers,
begin,
middle,
value,
currentLow,
currentUp).first;
int upperBound = getRange(
numbers,
middle,
end,
value,
currentLow,
currentUp).second;
returnstd::make_pair(lowerBound, upperBound);
}
}
Don't forget to include the required headers.
Don't forget to include the required headers.
