Binary search, when to use right = mid - 1, and when to use right = mid?

Question

I was working through this problem on leetcode https://leetcode.com/problems/leftmost-column-with-at-least-a-one/ and I cant think of an intuitive answer.

Why is the right (or high) pointer sometimes set to mid - 1, and why is it sometimes correct to set to mid?

I am aware that we must always set left = mid + 1 because of integer division. When only two elements remain, we need to set mid + 1 to avoid an infinite loop.

But what are the cases to use right = mid - 1, vs right = mid?

Thanks.

Porthole

Does this answer your question? Binary search Python Why do we use mid + 1 or mid - 1 – Informality

Not really. I’m interested in knowing when to apply mid - 1 vs just mid for the right value. – Porthole

It only depends on your implementation of the loop and calculation of mid. There's no particular "correct way" – Informality

If function implementation uses inclusive right border, you should right = mid-1, if not (like python ranges) - right = mid. – Heat

Answer 1

Let's say you are doing binary search on a sequence like below

.....0, 0, 0, 0, 1, 1, 1, 1, ....

Your decision function fn returns true if the value holds true for 1.

Now consider your target is to find the last position for 0. In each step of binary search, we will reduce search space such that we are certain the position is within the range. If fn returns true for mid you know that the last position for 0 will be less than mid (because you want the last occurrence of 0 which must be before the first occurrence of 1). So, you will update right=mid-1. If fn return false left=mid.

Now consider your target is to find the first occurrence for 1. Now if fn returns true you will update right=mid because you know the first occurrence of 1 will be on this position or left of it. In this case, if fn returns false, you will need to update left=mid+1.

Ilowell

Thanks, makes sense! – Porthole

adding on to this, is there any insight when to use terminating condition left < right, vs left <= right? – Porthole

When you decrease the interval in both direction you can use left <= right i.e., left=mid+1 and right=mid-1. Else you need to use left<right, since, otherwise you will be trapped in an infinite loop. – Ilowell

Answer 2

There are three templates to implement binary search
Template 1: No depend on other elements and neighbor elements.

while(left <= right){
    int mid = (int)Math.floor((left + right)/2);
    if(nums[mid] == target) return mid;
    else if(nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

Template 2: Use when searching a value requires accessing the current index and its immediate right neighbor's index

while(left < right){
   // Prevent (left + right) overflow
   int mid = left + (right - left) / 2;
   if(nums[mid] == target){ return mid; }
   else if(nums[mid] < target) {
      left = mid + 1; }
   else {
      right = mid; }
}

Template 3: Use when searching a value requires accessing the current index and both its immediate left and right neighbor's index

 while (left + 1 < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] < target) {
        left = mid;
    } else {
        right = mid;
    }
}

Source: LeetCode Explore

Gewgaw

Answer 3

Linear search on a small array outperforms binary search. Thus it should not really matter if you are using or not using -1, because your search should break out when right-left < N and then you can do a linear search between the two (N is a parameter which you can find for your particular application by running a benchmark).

Iirc N for integer numbers was ~700 when I measured it last.

Shreveport