Problem Statement:
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.
Approach:
- 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 issmaller → move left.1→ the picked number islarger → move right.
Repeatuntil the number is found.
Edge Case
Input: n= 1, pick = 1
Output: 1
Time & Space Complexity:
Time Complexity: O(logn)
Space Complexity: O(1)
Dry Run
Input: n = 10, pick = 6
Initial: l = 1, r = 10 Loop 1: m = Math.floor((1 + 10) / 2) = 5 guess(5) → too low → l = m + 1 = 6 Loop 2: m = Math.floor((6 + 10) / 2) = 8 guess(8) → too high → r = m - 1 = 7 Loop 3: m = Math.floor((6 + 7) / 2) = 6 guess(6) → correct → return 6
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;
}
}
};
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;
}
}
#include <iostream>
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;
}
#include <stdio.h>
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;
}
}
