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.
Examples:
Example 1:
Input: n = 10, pick = 6
Output: 6
Example 2:
Input: n = 1, pick = 1
Output: 1
Example 3:
Input: n = 2, pick = 1
Output: 1Solution in Python
Thought Process:
- Binary Search Basics:
- Start with a range of numbers from
1ton. - Calculate the middle of the range.
- Use the
guess()API to determine if the middle number is correct, too high, or too low. - Adjust the search range accordingly and repeat until we find the correct number.
- Start with a range of numbers from
- Using the
guess()API:- The API returns
0if the guessed number is correct. - It returns
-1if the guessed number is higher than the picked number. - It returns
1if the guessed number is lower than the picked number.
- The API returns
- Algorithm Steps:
- Set initial values for the search range:
left = 1andright = n. - While
leftis less than or equal toright:- Calculate the midpoint of the current range.
- Call
guess(mid).- If it returns
0, thenmidis the correct number, so returnmid. - If it returns
-1, adjust the search range to the left by settingright = mid - 1. - If it returns
1, adjust the search range to the right by settingleft = mid + 1.
- If it returns
- Set initial values for the search range:
Python
class Solution:
def guessNumber(self, n: int) -> int:
# Initialize the range for binary search
left, right = 1, n
# Binary search loop
while left <= right:
# Calculate the midpoint to guess
mid = left + (right - left) // 2
# Call the guess API with mid
result = guess(mid)
# Check the result of the guess
if result == 0:
# The guessed number is correct
return mid
elif result == -1:
# Guessed number is too high, search in the left half
right = mid - 1
else:
# Guessed number is too low, search in the right half
left = mid + 1Explanation of the Code:
- Initialize Range:
- We start with
leftas1andrightasn.
- We start with
- Binary Search Loop:
- Calculate the midpoint
midof the current range. - Call the
guess()function withmidto check if this is the correct number. - Adjust the search range based on the result:
- If
result == 0, we have guessed the correct number and returnmid. - If
result == -1, the guess is too high, so we adjustrighttomid - 1. - If
result == 1, the guess is too low, so we adjustlefttomid + 1.
- If
- Calculate the midpoint
Solution in C++
C++
class Solution {
public:
int guessNumber(int n) {
int left = 1; // Start of search range
int right = n; // End of search range
// Binary search loop until we find the correct number
while (left <= right) {
// Calculate the middle point to avoid overflow
int mid = left + (right - left) / 2;
int result = guess(mid); // Call the guess API
if (result == 0) {
// If guess(mid) returns 0, we've found the picked number
return mid;
} else if (result == -1) {
// If guess(mid) returns -1, the picked number is lower than mid
right = mid - 1;
} else {
// If guess(mid) returns 1, the picked number is higher than mid
left = mid + 1;
}
}
return -1; // This line will never be reached if the input is valid
}
};Solution in Javascript
JavaScript
var guessNumber = function(n) {
// Define the range of potential numbers
let left = 1;
let right = n;
// Continue the search until we find the correct number
while (left <= right) {
// Calculate the middle number of the current range
let mid = Math.floor((left + right) / 2);
// Call the `guess` API with the mid value
let result = guess(mid);
// If guess API returns 0, it means we've found the correct number
if (result === 0) {
return mid;
}
// If guess API returns -1, the picked number is lower, so we adjust the right bound
else if (result === -1) {
right = mid - 1;
}
// If guess API returns 1, the picked number is higher, so we adjust the left bound
else {
left = mid + 1;
}
}
};Solution in Java
Java
public class Solution extends GuessGame {
public int guessNumber(int n) {
// Initialize the low and high bounds for binary search
int low = 1;
int high = n;
// Loop until we find the number
while (low <= high) {
// Calculate the midpoint to make a guess
int mid = low + (high - low) / 2;
// Use the guess API to compare mid with the picked number
int result = guess(mid);
if (result == 0) {
// If the guess is correct, return the guessed number
return mid;
} else if (result == -1) {
// If the picked number is lower, adjust the high bound
high = mid - 1;
} else {
// If the picked number is higher, adjust the low bound
low = mid + 1;
}
}
// If the number was not found (should not happen with valid input)
return -1;
}
}