Binary search bounds

I had exactly the same issue until 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).

Hope this clarifies for whoever reads this. If anything is unclear of feels like magic please ping me to explain. 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.


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.

Tags:

Algorithm

Binary Search

Recent Posts