Elegant way of finding two consecutive values in sorted array that bound a given value?

Question

I have an array of sorted integers, and I'd like to get the two consecutive indices of elements that bound a particular value I pass in. To illustrate, because it's hard to describe in words, let's say I have an array (regular zero-indexed):

1 3 4 5 7 9

I want to get the two indices that bound, say, the value 6. In this case, the array has values 5 and 7 in consecutive positions, which bound the value I'm looking for (5 <= 6 <= 7), and so I'd return the index of 5 and the index of 7 (3 and 4, respectively).

I have this currently implemented in a very brute-force fashion, involving a lot of sorts and searches in the array. In addition, I feel like I'm missing a lot of corner cases (especially with values that are larger/smaller than the largest/smallest value in the array).

Is there an elegant way of doing this? What corner cases should I look out for, and how can I deal with and or check for them? Thanks!

Answer 1

Basically:

1. Sort the array (once);
2. Do a bisection search to find the closest element;
3. Compare that element to input value;
   • If it's lower you have the lower bound;
   • If it's higher you have the higher bound;
   • If it's the same you the bounds are next to the element.

Now if you can have repeat values in the array the last step is a little more complicated. You may need to skip over several values.

Ultimately this is little more than a bisection search on a sorted array, so is O(log n) on a sorted array and O(n log n) on an unsorted array.

Answer 2

One way to make this faster would be to use binary search. This will reduce your current time complexity of O(n) to O(log n).

Answer 3

Binary search for the value that you want (in this case, 6).

If it's found, grab the previous and next values based in the resulting index.

If not, your final search value will be either less than or greater than your target value. If it's bigger, your bounding values will be at that index and the one previous. Otherwise, they will be at that index and the next one.

Answer 4

You can solve the problem using binary search tol solve it in O(lg(n)) without considering so many boundary cases. The idea is to use binary search to find the lowest element greater than or equal to the value to bound (let's call it x).

pair<int, int> FindInterval(const vector<int>& v, int x) {
  int low = 0, high = (int)v.size();
  while (low < high) {
    const int mid = (low + high) / 2;
    if (v[mid] < x) low = mid + 1;
    else high = mid;
  }
  // This if is used to detect then a bound (a <= x <= x) is impossible but a
  // bound (x <= x <= can be found).
  if (low == 0 && low < (int)v.size() && v[low] == x) ++low;
  return make_pair(low - 1, low);
}

Notice that the answer might be (-1, 0), indicating that there is no lower bound for the interval, it might be (n - 1, n), indicating that there is no upper bound for the interval (where n is the size of v). Also, there can two possible answers if x is in v, and there can be multiple answers if x is multiple times in v, because the boundaries include the extremes.

Finally, you can substitute the binary search with the std::lower_bound function:

pair<int, int> FindInterval(const vector<int>& v, int x) {
  // This does the same as the previous hand-coded binary search.
  const int low = (int)(lower_bound(v.begin(), v.end(), x) - v.begin());

  // The rest of the code is the same...
}