Description
Bug Report for https://neetcode.io/problems/guess-number-higher-or-lower
Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.
Hey - thanks for a great product it's really helping me prepare for an interview.
The binary search solution for C# is incorrect - it just repeats the brute force solution.
Here is a working binary search C# implementation:
Note having to cast at least one of the low and high values to a long value during calculation of midpoint (I've done both for clarity but it's not strictly necessary). Otherwise we can overflow max int and get a negative midpoint value, and an infinite loop, given that n can be == int.MaxValue. Once we divide by 2 we're always guaranteed to be back within the bounds of an int so we can safely re cast. In my mind this takes this question from an easy to a mid, at least for C#!
public static int GuessNumber(int n)
{
var low = 1;
var high = n;
while (true)
{
long midLong = ((long)low + (long)high) / 2;
var mid = (int)midLong;
var result = guess(mid);
if (result == 0)
{
return mid;
}else if (result == -1)// guess too high
{
high = mid - 1;
} else if (result == 1) // guess too low
{
low = mid + 1;
}
}
}