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

user_7065093 0
Viewed 1077

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.

binary-search pointers sorting algorithm
3 Answers

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.

user_51312870

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.

user_33487790

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

user_171036350
Related