This problem uses binary search to find a hidden number between 1 and n using a feedback API guess(num), which tells us whether our guess is too high, too low, or correct.
Steps
- Initialize two pointers:
l = 1andr = n. - Use binary search to guess the middle number
m. - If
guess(m)returns:0→mis the correct number-1→ the picked number is smaller → move left1→ the picked number is larger → move right
- Repeat until the number is found.
Dry Run
Input: n = 10, pick = 6
- Guess 5 → too low
- Guess 8 → too high
- Guess 6 → correct
Output: 6
Edge Case
Input: n = 1, pick = 1
Output: 1
Time & Space Complexity
- Time Complexity: O(log n)
- Space Complexity: O(1)
var guessNumber = function(n) {
let l = 1;
let r = n;
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
let res = guess(m);
if (res === 0) {
return m;
} else if (res < 0) {
r = m - 1;
} else {
l = m + 1;
}
}
};
int guessNumber(int n) {
int l = 1, r = n;
while (l <= r) {
int m = l + (r - l) / 2;
int res = guess(m);
if (res == 0) return m;
else if (res < 0) r = m - 1;
else l = m + 1;
}
return -1;
}
int guessNumber(int n) {
int l = 1, r = n;
while (l <= r) {
int m = l + (r - l) / 2;
int res = guess(m);
if (res == 0) return m;
else if (res < 0) r = m - 1;
else l = m + 1;
}
return -1;
}
public class Solution {
public int guessNumber(int n) {
int l = 1, r = n;
while (l <= r) {
int m = l + (r - l) / 2;
int res = guess(m);
if (res == 0) return m;
else if (res < 0) r = m - 1;
else l = m + 1;
}
return -1;
}
}
def guessNumber(n):
l, r = 1, n
while l <= r:
m = l + (r - l) // 2
res = guess(m)
if res == 0:
return m
elif res < 0:
r = m - 1
else:
l = m + 1
return -1
public class Solution {
public int GuessNumber(int n) {
int l = 1, r = n;
while (l <= r) {
int m = l + (r - l) / 2;
int res = Guess(m);
if (res == 0) return m;
else if (res < 0) r = m - 1;
else l = m + 1;
}
return -1;
}
}
