
Description
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 three possible results:
- 1: Your guess is higher than the number I picked (i.e. num > pick).
- 1: Your guess is lower than the number I picked (i.e. num < pick).
- 0: your guess is equal to the number I picked (i.e. num == pick).
Return the number that I picked.
Guess Number Higher or Lower
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 three possible results:
-1
: Your guess is higher than the number I picked (i.e.,num > pick
).1
: Your guess is lower than the number I picked (i.e.,num < pick
).0
: Your guess is equal to the number I picked (i.e.,num == pick
).
Return the number that I picked.
Intuition
The problem is a classic example of a binary search problem. The key observation is that each response from the guess
API helps to eliminate half of the search space, which makes the binary search approach particularly efficient.
Approach
- Initialize the Search Space: Start with the full range from 1 to
n
. - Binary Search:
- Compute the middle point of the current range.
- Use the
guess
API to check if the middle point is the correct number. - If the result is0
, then the middle point is the correct guess. - If the result is-1
, the correct number is smaller, so adjust the right boundary tomid - 1
. - If the result is1
, the correct number is larger, so adjust the left boundary tomid + 1
. - Repeat the Process: Continue the process until the correct number is found.
Complexity
Time Complexity:
O(log n)
- Each guess reduces the search space by half, leading to a logarithmic number of guesses.
Space Complexity:
O(1)
- The algorithm only uses a few variables for the search boundaries and the middle point, making the space usage constant.
Code
C++
class Solution {
public:
int guessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int result = guess(mid);
if (result == 0) {
return mid;
} else if (result > 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
Python
class Solution:
def guessNumber(self, n: int) -> int:
left, right = 1, n
while left <= right:
mid = (left + right) // 2
result = guess(mid)
if result == 0:
return mid
elif result > 0:
left = mid + 1
else:
right = mid - 1
return -1
Java
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int result = guess(mid);
if (result == 0) {
return mid;
} else if (result > 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
JavaScript
/**
* @param {number} n
* @return {number}
*/
var guessNumber = function (n) {
let right = n
let left = 0
while (left <= right) {
let mid = Math.floor((right + left) / 2)
const result = guess(mid)
if (result > 0) {
left = mid + 1
} else if (result < 0) {
right = mid
} else {
return mid
}
}
return -1
};