Standard binary search but got TLE


  • 1
    J
    class Solution {
    public:
        int guessNumber(int n) {
            int x = (1 + n) >> 1, l = 1, h = n;
            int g = guess(x);
            while(g != 0) {
                if(g == -1) {
                    l = x + 1;
                    x = (l + h) >> 1;
                    g = guess(x);
                } else {
                    h = x - 1;
                    x = (l + h) >> 1;
                    g = guess(x);
                }
            }
            return x;
        }
    };
    

    the code is very simple, can anyone explain for me why I got TLE? Thank you


  • 0
    S

    Just take long long int to calculate x , because in some case addition goes out of range.
    for example : 2126753390 . in this case l+h goes out of range.


  • 0
    J

    @SamAmre it got TLE just tge furst test case (10, 6)


  • 0
    T

    @jtimberlakers please review the question again,guess return 1 when x < target number


  • 0
    S

    @jtimberlakers just read the question .. you have misunderstood the guess() function . just swap the code between the if(g == -1) and else one in while loop.


  • 1

    Two problems in your solution:

    • just SamAmre pointed you should use l+(h-l) to avoid overflow
    • your understanding of guess is opposite, as tutu509 said; return -1 indicates that your number m is higher A.K.A my number is lower indicated in problem.

    Here is your solution but corrected

    int guess(int num);
    class Solution {
    public:
        int guessNumber(int n) {
            int x = 1+(n-1)/2, l = 1, h = n;
            int g = guess(x);
            while(g != 0) {
                if(g == -1) {
                    h = x - 1;
                    x = l+(h-l)/2;
                    g = guess(x);
                } else {
                    l = x + 1;
                    x = l+(h-l)/2;
                    g = guess(x);
                }
            }
            return x;
        }
    };
    

  • 0
    J

    @LHearen Thank you all for the help. I've corrected my code and now passed


Log in to reply
 

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