My java code beats 99.8% 16ms (sometimes)


  • 0
    /* 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 l=1,r=n;
            while(l<r){
                int mid=l+((r-l)>>1);
                if (!isBadVersion(mid)) l = mid + 1;
                else r = mid;   
            }
            return l;
        }
    }

  • 0
    H

    your shift operator almost got me :), however, I found it actually slower than division operator ...


  • 0
    Z

    Can you tell me why I use:
    int mid = first+((last-first)>>1);
    as you did, answer is accepted, but when I write:
    int mid = (last+first)>>1;
    it will exceed time limit.

    Just because the first one avoided large number, so that right shift is more fast?


  • 0

    last + first will larger than the Integer.MAX_VALUE, so the answer will be wrong.U can submit it to check it.

    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            long l=1,r=n;
            while(l<r){
                long mid=(l + r)>>1;
                if (!isBadVersion((int)mid)) l = mid + 1;
                else r = mid;   
            }
            return (int)l;
        }
    }

Log in to reply
 

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