Dare2Solve
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.
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.
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.
Initialize the Search Space: Start with the full range from 1 to n
.
Binary Search:
guess
API to check if the middle point is the correct number.0
, then the middle point is the correct guess.-1
, the correct number is smaller, so adjust the right boundary to mid - 1
.1
, the correct number is larger, so adjust the left boundary to mid + 1
.Repeat the Process: Continue the process until the correct number is found.
O(log n)
- Each guess reduces the search space by half, leading to a logarithmic number of guesses.
O(1)
- The algorithm only uses a few variables for the search boundaries and the middle point, making the space usage constant.
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;
}
};
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
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;
}
}
/**
* @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
};