311. Guess Number Higher or Lower
I'm thinking of a number between 1 and n. You can't see it — but you may ask about any candidate x through an oracle function guess(x), which answers:
0—xis my number,-1—xis too high (my number is smaller),1—xis too low (my number is larger).
Your function receives n and the guess oracle, and returns the secret number. Asking about every candidate works; aim to need only a handful of questions even when n is a million.
(The harness builds the oracle for you from the test input — your code only ever talks to guess.)
Example 1:
Input: n = 10, guess built with pick = 6
Output: 6
Explanation: guess(5) answers 1 (too low), guess(8) answers -1 (too high), guess(6) answers 0 — found in three questions.
Example 2:
Input: n = 1, guess built with pick = 1
Output: 1
Explanation: With n = 1 there is only one possible number, so the first question already confirms it.
Constraints:
- 1 ≤ n ≤ 10⁶
- 1 ≤ pick ≤ n
Hints:
Asking guess(1), guess(2), guess(3), … eventually finds the number, but needs up to n questions.
Every answer from the oracle rules out an entire side of the remaining range. Which candidate splits the remaining range most evenly?
Keep a window [lo, hi] that must contain the secret. Ask about the middle; shrink to the half the oracle points at. That's log2(n) questions — about 20 for a million.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 10, pick = 6
Expected output: 6