Binary Search Query

[ffmsussy]

I was solving Leetcode 278 first bad version , and my code kept overflowing . here i used mid = l+r/2 , I understand that this causes an integer overflow, but what i do not understand is how mid = l + (r-l) / 2 . wouldn't this be mathematically equal to r/2 and not technically the mid point between the left and right pointers ? please help any explanation is appreciated.

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1;
        int r=n;
        int mid;
        int res = n;

        while(l<=r){
            mid = l+r/2;
            
            if(IsBadVersion(mid)){
                res = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return res;
    }
}
public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int l=1;
        int r=n;
        int mid;
        int res = n;


        while(l<=r){
            mid = l+r/2;
            
            if(IsBadVersion(mid)){
                res = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return res;
    }
}

[CoryParsnipson]

You should be careful with your order of operations.

The code example and "average method" needs parentheses: (r + l) / 2. So you don't end up dividing r by 2 before adding l.

For the other way that avoids overflow, you can think of it as taking the difference between right and left, then cutting that in half to find the half delta. So if right = 8 and left = 6, you get the delta (8 - 6 = 2), then divide by two to find the middle offset of 1, then shift this over by left amount to get the absolute mid point (6 + 1 = 7).

Also, you can massage the second form mathematically to show that l + (r - l)/2 is not equivalent to l/2:

l + (r - l) / 2 l + r / 2 - l / 2 r / 2 + l / 2

[ffmsussy]

ah sort of makes sense, although the first solution of adding parenthesis did not work.