Problem: We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns 3 possible results:
- -1: The number I picked is lower than your guess (i.e. pick < num).
- 1: The number I picked is higher than your guess (i.e. pick > num).
- 0: The number I picked is equal to your guess (i.e. pick == num).
Return the number that I picked.
Example:
Input: n = 10, pick = 6 Output: 6
Input: n = 1, pick = 1 Output: 1
Input: n = 2, pick = 1 Output: 1
Input: n = 2, pick = 2 Output: 2
Approach: It's a straight forward binary search problem. You can look at the implementation to understand the approach.
Implementation in C#:
public int GuessNumber(int n)
{
int start = 0, end = n;
while (start <= end)
{
int mid = start + (end - start) / 2;
int guessRes = guess(mid);
if (guessRes == 0)
{
return mid;
}
else if(guessRes == -1)
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return -1;
}
Complexity: O(logn)
No comments:
Post a Comment