Guess Number Higher or Lower


  • 0

    Click here to see the full article post


  • 1

    The binary search can be shorter and faster by not special-treating the unlikely guess(mid) == 0 case. Also, >>> is apparently much faster than /:

    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (guess(mid) <= 0)
                high = mid;
            else
                low = mid + 1;
        }
        return low;
    }
    

    Using the following wrapper to magnify the time, your solution got accepted in around 133 ms while mine got accepted in around 68 ms (and around 122 ms when still using the / way to compute mid).

    public int guessNumber(int n) {
        long answer = 0;
        for (int i=0; i<100000; i++)
            answer += realGuessNumber(n);
        return (int) (answer / 100000);
    }
    

    A question about yours: Why check res == 0 first? That's the most unlikely case. It rarely happens. So most of the time you'll also need the res < 0 check. If you instead test that one first, then about half of the time you can expect to only need that one check and go to the next iteration right away.


  • 0
    A

    In Binary Search, why does the Time Limit exceed if I use,
    mid = (high + low) / 2;


  • 0
    W

    ashwin88 it's because of overflow. Basically the sum doesn't do anything special with the sign bit and so sums greater than 2^31-1 but less than 2^32-1 will be negative. For example, if you added 1 to 2^31-1, you'd get int32.minvalue, or -2^31. Lets use a smaller example, say an 8bit number, the max signed value you can store is 01111111, which is 127. If you add one, what do you expect to get as a result? It should be 10000000, which is -128. Due to this overflow, your code is infinitely looping from positive to negative.

    In C# there's a compiler flag (checked) that will throw an exception for overflow/underflow, but the default behavior is the same as java/c++ with "wrapping" or modulo 2^bitcount of your number type.

    In case that didn't make sense or you want to learn more, refer to this article to learn more about exactly what number your sum is becoming: http://www.cplusplus.com/articles/DE18T05o/


  • 0
    W
    This post is deleted!

  • 0
    S

    @ashwin88, because for the big input 1702766719 & 2126753390.
    (high+low) overflows Integer limit in the first place.


  • 0
    R

    Could you explain why Ternary Search is faster for this specific question? Thanks!


  • 0
    C

    For some reason, I have binary search, but it exceeds the time limit. It's a basic while loop that switches high and low while only running while guess(num)!=0. Any reasons why this happens? Code:

            int low = 1;
            int high = n;
            while(guess(num)!=0){
                if(guess(num)>0)
                    low = num + 1;
                    
                else
                    high = num;
                    
                num = (low + high)/2;
                System.out.println("One loop");
                    
            }
            return num;```

  • 0
    C

    Also I do not print to console when submitting.


  • 0
    F

    Why isn't this problem available with JavaScript when its follow-up is?


  • 0
    C

    @cronk
    Use long instead of int. You are getting integer overflow from (low + high).


  • 0
    S

    Can you help understand the constant term 2 and 4 in equations -
    T(n) = T(n/2) + 2 <--- is 2 = 1 (for splitting) and 1 for comparison?
    T(n) = T(n/3) + 4 <--- is 4 = 1(for splitting) and 3 for comparison?


  • 0
    Y

    Why do you compare B-Search and T-Search using worst situation instead of average situation? In my opinion, average situation is more convinced.


Log in to reply
 

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