SImple binary search solution o(log n)


  • 3
    A
    /* The isBadVersion API is defined in the parent class VersionControl.
          boolean isBadVersion(int version); */
    // Assuming version number starts with 1
    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int start = 1;
            int end = n;
            while (start < end){
                int mid = start + (end - start)/2;
                if (isBadVersion(mid)){
                    end = mid;
                }
                else {
                    start = mid + 1;
                }
            }
            return start;
        }
    }

  • 0
    S

    Hi , I meet a problem according to your code , I will appreciate it if you can solve it for me.
    The problem is : if I change the code "int mid=start+(end-start)/2" to "int mid=(start+end)/2" , it will TLE , what's wrong with that?


  • 0
    A

    Because your ( Start + end ) value can go beyond Integer.MAX_VALUE and hence giving you a negative value.
    Eg : start = 1073741824 , end = 1073741827
    if mid = (start + end) /2 the mid = 2147483651/2

    Here the numerator is more than the integer range in java. hence making mid = -2147483644/2 = -1073741822 which is wrong

    if mid = start + (end - start)/2 then
    mid = 1073741824 + 1 = 1073741825

    I hope this is helpful! :)


Log in to reply
 

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