# Guess Number Higher or Lower

• 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) {
for (int i=0; i<100000; i++)
}
``````

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.

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

• 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.

• This post is deleted!

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

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

• 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;`````````

• Also I do not print to console when submitting.

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

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

• 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?

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

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