Find occurrences of an integer in a sorted array

    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:

// 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.