Guess Number Higher or Lower


The binary search can be shorter and faster by not specialtreating 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 theres < 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.

ashwin88 it's because of overflow. Basically the sum doesn't do anything special with the sign bit and so sums greater than 2^311 but less than 2^321 will be negative. For example, if you added 1 to 2^311, 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/

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

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