O(lgN) simple Java solution


  • 95

    The binary search code:

    public int firstBadVersion(int n) {
        int start = 1, end = n;
        while (start < end) {
            int mid = start + (end-start) / 2;
            if (!isBadVersion(mid)) start = mid + 1;
            else end = mid;            
        }        
        return start;
    }

  • 6
    P
     public int firstBadVersion(int n) {
            return binarySearch(1,n);
        }
        
         public int binarySearch(int start, int end) {
            long startLong = start;
            long endLong = end;
            Long middleLong = (startLong + endLong) / 2;
            int middle = middleLong.intValue();
            
            if (isBadVersion(middle)) {
                if (!isBadVersion(middle-1)) {
                    return middle;
                }
    
                return binarySearch(start,middle);
            } else {
                if (isBadVersion(middle+1)) {
                    return middle+1;
                }
    
                return binarySearch(middle + 1, end);
            }
         }

  • 25
    L

    if I use 'int mid = (left + right)/2;' in the while sentance,the program will apear error 'Time Limit Exceeded'. Why? Thank you!


  • 17

    Hi, lixiao, if left and right are both very large, their sum will exceed integer limit


  • 0
    J

    Greate! I encountered the same issue. And your method works well. Thanks.


  • 0

    Very nice explanation, I am stuck at strange RunTime errors, so this is the issue


  • 0

    very simple and concise


  • 2
    L

    I think there is no need to use long.We can use "int mid = start + (end-start) / 2;" to solve the problem.


  • 0
    E

    why can't use mid = (start+end) / 2?


  • 1
    E

    I think they are the same.

    Edit: my above comment is WRONG! My understanding is that start + (end-start) / 2 can avoid possible overflow, for example start = 2^20 and end = 2^30.


  • 0

    if start and end are both very large, their sum will exceed integer limit


  • 0
    T

    thanks, i see!


  • 0
    E

    What I learnt from a Google software engineer is that this kind of possible overflow will not affect the interview because overflow is NOT the focus of this test problem. So don't pay too much attention to it if you are not so used to considering overflow.


  • 1
    E

    What I learnt from a Google software engineer is that this kind of possible overflow will not affect your interview performance because overflow is NOT the focus of this test problem. So don't worry too much even if you are not so used to considering overflow. However, if the test problem is on overflow, then you have to be careful not to miss it.


  • 1
    E

    shame on those giving out "random" down votes without any explanation. If you disagree, please leave your thoughts here so others can possibly learn from you.


  • 0
    Z

    how about the n is only 1 and 1 is not bad version?


  • 0
    H

    the problem said there must be a bad version


  • 0
    B

    @lixiaolun overflow issue.


  • 1
    P

    Recommended way to avoid overflow in Java when calculating mid is to use the unsigned right shift operation (>>>):

    int mid = (from + to) >>> 1;
    

  • 0
    G

    Another option to avoid overflow : subtract

             int cursor = n, good = 0, bad = n;
             while(bad - good > 1) {
                if(isBadVersion(cursor)) {
                    bad = cursor;
                    cursor = (bad - good)/2;
                } else {
                    good = cursor;
                    cursor += (bad - good)/2;
                }
            }
            
            return bad;
    

Log in to reply
 

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