Anyone think the standard binary search solution is risky?


  • 0
    H

    The following solution works well for finding first bad version, but if we were to find the last food version. The same approach has the risk being locked on left border of the searching interval. e.g. in case of [2,3] , 2+(3-2)/2 always gives 2.

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

  • 0
    H

    sorry, I want to say "last good version"


Log in to reply
 

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