My Java Solution using Binary Search


  • 1
    R
    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int low  = 1;
            int high = n;
            int mid = 1;
            
            while(low <= high){
                if(low == high)
                    return low;
                mid = (low + (high - low)/2);
                if(isBadVersion(mid)){
                    high = mid;
                }
                else{
                    low =  mid + 1;
                }
            }
            return mid ;
        }
    }

  • 0
    This post is deleted!

  • 0

    why mid = (low + (high - low )/2) ? why not mid = (low + high)/2


  • 1

    @wwt_1991 (low + high) might overflow if they are very big, and their sum could be bigger than (pow(2, 32) - 1). so the result won't be correct.
    (low + (high - low )/2) doesn't have this issue.


  • 0

    @qiuping345 thanks


  • 0
    E

    @wwt_1991 I would actually suggest (low/2+high/2) (I see it as more readable than the posted solution). The reason you want to avoid (low+high)/2 is because you may run into a situation where the version numbers add up a number higher than maximum allowable value for an int in Java. You avoid that by dividing the high and low before summing them.
    *Whoops! Didn't realize someone already answered. I'll just leave this here anyway.


Log in to reply
 

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