Guess the Number

L5 Medium Binary Search

Concept

Binary search also applies when the only feedback is "too high" or "too low" — that is exactly the guess loop everyone plays with numbers.

A number between 1 and n is chosen. A guess helper returns -1 if your guess is too low, 1 if too high, and 0 on a match. Return the chosen number.

Examples

▸ n = 10, pick = 6

→ 6

▸ n = 1, pick = 1

→ 1

▸ n = 100, pick = 50

→ 50

Progressive Hints

Hint 1 · Nudge

Use the helper as the signal for which half of the range still holds the answer.

Hint 2 · Plan

Binary search through 1 to n. Guess the midpoint and ask the helper: too low means search higher, too high means search lower, and 0 means you found it.

Hint 3 · Approach

lo = 1, hi = n. While lo <= hi: mid = the middle; c = guess(mid); if c == 0 return mid; if c says too low, lo = mid + 1; else hi = mid - 1.

Output

// Run your code to see the output here.