Java log(n) solution using binary search


  • 0
    I
    /* The isBadVersion API is defined in the parent class VersionControl.
          boolean isBadVersion(int version); */
    
    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            
            int left = 0, right = n;
            while(left <= right) {
                int mid = left + (right - left) / 2;
                
                if(isBadVersion(mid)) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if(!isBadVersion(right)) {
                return right + 1;
            }
            
            return right;
        }
    }
    

  • 0
    J

    @ilakhmedov You have redudant API call there. In the last iteration if left == right you check if mid is bad, if it is good though, right is not being changed. And if it is good, you move right to an index, you have already checked. Still you call the api another time after the loop

    if(!isBadVersion(right)) {
                return right + 1;
            }
    

    If would recommend changing the while condition to left < right.


Log in to reply
 

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