Binary search bounds

Question

I always have the hardest time with this and I have yet to see a definitive explanation for something that is supposedly so common and highly-used.

We already know the standard binary search. Given starting lower and upper bounds, find the middle point at (lower + higher)/2, and then compare it against your array, and then re-set the bounds accordingly, etc.

However what are the needed differences to adjust the search to find (for a list in ascending order):

1. Smallest value >= target
2. Smallest value > target
3. Largest value <= target
4. Largest value < target

It seems like each of these cases requires very small tweaks to the algorithm but I can never get them to work right. I try changing inequalities, return conditions, I change how the bounds are updated, but nothing seems consistent.

What are the definitive ways to handle these four cases?

Answer 1

Binary search(at least the way I implement it) relies on a simple property - a predicate holds true for one end of the interval and does not hold true for the other end. I always consider my interval to be closed at one end and opened at the other. So let's take a look at this code snippet:

int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in

while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (pred(a[mid])) {
    beg = mid;
  } else { 
    end = mid;
  }
}
// answer is at a[beg]

This will work for any of the comparisons you define. Simply replace pred with <=target or >=target or <target or >target.

After the cycle exits, a[beg] will be the last element for which the given inequality holds.

So let's assume(like suggested in the comments) that we want to find the largest number for which a[i] <= target. Then if we use predicate a[i] <= target the code will look like:

int beg = 0; // pred(beg) should hold true
int end = n;// length of an array or a value that is guranteed to be out of the interval that we are interested in
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] <= target) {
    beg = mid;
  } else { 
    end = mid;
  }
}

And after the cycle exits, the index that you are searching for will be beg.

Also depending on the comparison you may have to start from the right end of the array. E.g. if you are searching for the largest value >= target, you will do something of the sort of:

beg = -1;
end = n - 1;
while (end - beg >  1) {
  int mid = (end + beg) / 2;
  if (a[mid] >= target) {
    end = mid;
  } else { 
    beg = mid;
  }
}

And the value that you are searching for will be with index end. Note that in this case I consider the interval (beg, end] and thus I've slightly modified the starting interval.

Answer 2

The basic binary search is to search the position/value which equals with the target key. While it can be extended to find the minimal position/value which satisfy some condition, or find the maximal position/value which satisfy some condition.

Suppose the array is ascending order, if no satisfied position/value found, return -1.

Code sample:

  // find the minimal position which satisfy some condition
  private static int getMinPosition(int[] arr, int target) {
      int l = 0, r = arr.length - 1;
      int ans = -1;
      while(l <= r) {
          int m = (l + r) >> 1;
          // feel free to replace the condition
          // here it means find the minimal position that the element not smaller than target
          if(arr[m] >= target) {
              ans = m;
              r = m - 1;
          } else {
              l = m + 1;
          }
      }
      return ans;
  }

  // find the maximal position which satisfy some condition
  private static int getMaxPosition(int[] arr, int target) {
      int l = 0, r = arr.length - 1;
      int ans = -1;
      while(l <= r) {
          int m = (l + r) >> 1;
          // feel free to replace the condition
          // here it means find the maximal position that the element less than target
          if(arr[m] < target) {
              ans = m;
              l = m + 1;
          } else {
              r = m - 1;
          }
      }
      return ans;
  }

    int[] a = {3, 5, 5, 7, 10, 15};
    System.out.println(BinarySearchTool.getMinPosition(a, 5));
    System.out.println(BinarySearchTool.getMinPosition(a, 6));
    System.out.println(BinarySearchTool.getMaxPosition(a, 8));

Answer 3

What you need is a binary search that lets you participate in the process at the last step. The typical binary search would receive (array, element) and produce a value (normally the index or not found). But if you have a modified binary that accept a function to be invoked at the end of the search you can cover all cases.

For example, in Javascript to make it easy to test, the following binary search

function binarySearch(array, el, fn) {
    function aux(left,  right) {
        if (left > right) {
            return fn(array, null, left, right);
        }

        var middle = Math.floor((left + right) / 2);
        var value = array[middle];

        if (value > el) {
            return aux(left, middle - 1);
        } if (value < el) {
            return aux(middle + 1, right);
        } else {
            return fn(array, middle, left, right);
        }
    }

    return aux(0, array.length - 1);
}

would allow you to cover each case with a particular return function.

• default
  function(a, m) { return m; }
• Smallest value >= target
  function(a, m, l, r) { return m != null ? a[m] : r + 1 >= a.length ? null : a[r + 1]; }
• Smallest value > target
  function(a, m, l, r) { return (m || r) + 1 >= a.length ? null : a[(m || r) + 1]; }
• Largest value <= target
  function(a, m, l, r) { return m != null ? a[m] : l - 1 > 0 ? a[l - 1] : null; }
• Largest value < target
  function(a, m, l, r) { return (m || l) - 1 < 0 ? null : a[(m || l) - 1]; }

Answer 4

I figured out loop invariants along with predicates are the best and most consistent way of approaching all binary problems.

Point 1: Think of predicates
In general for all these 4 cases (and also the normal binary search for equality), imagine them as a predicate. So what this means is that some of the values are meeting the predicate and some some failing. So consider for example this array with a target of 5: [1, 2, 3, 4, 6, 7, 8]. Finding the first number greater than 5 is basically equivalent of finding the first one in this array: [0, 0, 0, 0, 1, 1, 1].

Point 2: Search boundaries inclusive
I like to have both ends always inclusive. But I can see some people like start to be inclusive and end exclusive (on len instead of len -1). I like to have all the elements inside of the array, so when referring to a[mid] I don't think whether that will give me an array out of bound. So my preference: Go inclusive!!!

Point 3: While loop condition <=
So we even want to process the subarray of size 1 in the while loop, and when the while loop finishes there should be no unprocessed element. I really like this logic. It's always solid as a rock. Initially all the elements are not inspected, basically they are unknown. Meaning that everything in the range of [st = 0, to end = len - 1] are not inspected. Then when the while loop finishes, the range of uninspected elements should be array of size 0!

Point 4: Loop invariants
Since we defined start = 0, end = len - 1, invariants will be like this: Anything left of start is smaller than target. Anything right of end is greater than or equal to the target.

Point 5: The answer
Once the loop finishes, basically based on the loop invariants anything to the left of start is smaller. So that means that start is the first element greater than or equal to the target. Equivalently, anything to the right of end is greater than or equal to the target. So that means the answer is also equal to end + 1.

The code:

public int find(int a[], int target){
  int start = 0; 
  int end = a.length - 1; 
  while (start <= end){
    int mid = (start + end) / 2; // or for no overflow start + (end - start) / 2
    if (a[mid] < target) 
       start = mid + 1; 
    else // a[mid] >= target
       end = mid - 1; 
  }
  return start; // or end + 1;
}

variations:
<
It's equivalent of finding the first 0. So basically only return changes.

return end; // or return start - 1; 

>
change the if condition to <= and else will be >. No other change.

<=
Same as >, return end; // or return start - 1;

So in general with this model for all the 5 variations (<=, <, >, >=, normal binary search) only the condition in the if changes and the return statement. And figuring those small changes is super easy when you consider the invariants (point 4) and the answer (point 5).

After understanding this method, everything for binary search should be as clear as day!

Extra point: It would be a good practice to also try including the start but excluding the end. So the array would be initially [0, len). If you can write the invariants, new condition for the while loop, the answer and then a clear code, it means you learnt the concept.