Recently I was given a problem to solve during a technical interview: we have an array of sorted integers as an input and a single integer; we need to find the starting and ending positions of the occurrences of that integer in the array. For example, if the array is {0, 1, 1, 2, 3, 4, 4, 4, 5} and the input integer is 1, the program should return (1, 2). If the input integer is 4 and the array is the same, the program should return (5, 7). And finally, if no occurrence found, say if the input is 7, the program should return (-1, -1). I couldn't get a clean code in the assigned time, that's why I decided to try it at home and make sure my algorithm works. So here is just a simple solution. For simplicity, I used std::vector<int> as an input array, but obviously it should be a generalized function with a template parameter. Anyway, here is my solution:
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:
// 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.
int middle = begin + (end - begin) / 2;
// 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;
return
std::make_pair(lowerBound, upperBound);
}
}
Don't forget to include the required headers.
Don't forget to include the required headers.
