Binary Search and Gotchas

 Binary search is an important algorithm because it helps find certain element's position fairly quickly even when there are vary large number of elements.

Given a sorted integer array, and a target, find the index of target in the array. If its not present, return -1.

Say there might be duplicates in the array. Return the leftmost index of target in the array.

    int findLeft(int[] nums, int target) {
        if(nums.length==0) return -1;
        if(nums.length==1) return nums[0]==target ? 0 : -1;
        
        int left = 0, right = nums.length-1;
        while(left < right) {
            int mid = left + (right-left)/2;
            
            if(nums[mid] > target) {
                right = mid-1;
            } else if(nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
    
  

To find the left most index, the above code will work fine. There are some number properties working in the background to make the above code successful.

The mid is calculated dividing the diff of right and left by 2. What if the difference is 1. In that case the mid is same as left. But in this case, right is assigned to mid, so the algorithm will terminate in the next step.

What if you have to find the right most index of the target element in the array.

    int findRight(int[] nums, int target) {
        if(nums.length==0) return -1;
        if(nums.length==1) return nums[0]==target ? 0 : -1;
        
        int left = 0, right = nums.length-1;
        while(left < right) {
            int mid = left + (right-left)/2;
            
            if(nums[mid] > target) {
                right = mid-1;
            } else if(nums[mid] < target){
                left = mid+1  ;
            } else {
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }

Do you think the above code will work? Why or Why not?

All the calculations are same as the previous code except, when the mid and target are equal, you are assigning mid to left. This is because there may be other duplicated on the right of mid which you intend to search. But if there's not, you still want the right to be able to come to left before terminating.

But what about the calculation of mid? say the diff between right and left is 1 at some step. Then the mid will be same as left. Then in action, you again assign left to mid. So there will be an infinite loop.

How to solve this issue?

How about adding 1 to the diff of right and left before dividing it by 2. Do you think that has any adverse effect in the result?

Why or Why not?

    int findRight(int[] nums, int target) {
        if(nums.length==0) return -1;
        if(nums.length==1) return nums[0]==target ? 0 : -1;
        
        int left = 0, right = nums.length-1;
        while(left < right) {
            int mid = left + (right-left+1)/2;
            
            if(nums[mid] > target) {
                right = mid-1;
            } else if(nums[mid] < target){
                left = mid+1  ;
            } else {
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }

For the intermediate mids, this algorithm will pick the right one among the two middles. But the overall result will be correct and this algorithm will terminate as well. Why?

Because when diff of right and left is 1, mid will be left + 1, which would be larger than target (if left is the rightmost target). In this case, right will decrease to left and the loop terminates in the next step.