0ms c++ binary search


  • 14
    D
    int guessNumber(int n) {
            int maxNumber = n, minNumber = 1;
            while (true) {
                int meanNumber = (maxNumber - minNumber) / 2 + minNumber;
                // Do NOT use (maxNumber+minNumber)/2 in case of over flow
                int res = guess(meanNumber);
                if (res == 0) { 
                    return meanNumber;
                } else if (res == 1) {
                    minNumber = meanNumber + 1;
                } else {
                    maxNumber = meanNumber - 1;
                }
            }
        }
    

  • 3
    K

    Thanks,I used (max+min)/2 and got TLE...


  • 1
    C

    @KrisW integer overflow


  • 0
    W

    thx , i just got the same problem = =


  • 0
    J

    why int TLE?can you explain it?


  • 0
    P

    I also made the same mistake that the description of problem is a little bit ambiguous. Actually, if the guess number is lower, the API return 1; if the guess number is higher, the API return -1; if they are equal, it returns 0.


  • 0
    W

    @pkuzw You are right. Thanks.


  • 0
    F

    @KrisW said in 0ms c++ binary search:

    Thanks,I used (max+min)/2 and got TLE...

    Me too.


  • 0
    F

    Why using (max + min) / 2 will get TLE,but min + (max - min) / 2 is accepted.Logically speaking,even if the latter one will overflow,not TLE instead.


  • 1
    S

    cos low+high will exceed, so we should use long mid, instead of int, but the API guess(int) means we can't use long, thus we can only use low + (high-low)/2 (equal to (low+high)/2 in math)


  • 0
    E

    Thanks for your sharing, to prevent the over flow, simply do:

    double maxNumber = n, minNumber = 1;
    double meanNumber = (maxNumber +minNumber) / 2
    

    would solve it and still 0ms
    Please feel free to give a try:)


Log in to reply
 

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