Why (left + right) / 2 got TLE but (left + (right - left) / 2) got AC?


  • 0
    A

    here's my code

    public int firstBadVersion(int n) {
        int left = 1, right = n;
        int min = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            boolean bad = isBadVersion(mid);
            if (bad) {
                min = Math.min(min, mid);
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return min;
    }

  • 15
    M

    Because,

    (left + right) / 2
    

    can lead to an overflow.


  • 0
    A

    I see! Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.