DSA problem
Guess Number Higher or Lower
We are playing the Guess Game. I pick a number from 1 to n. Each time you guess a number, I give you one of three feedbacks: -1 (my number is lower than your guess, so go lower), 1 (my number is higher than your guess), or 0 (you guessed right).
You call the pre-defined API int guess(int num) to make a guess. Your job is to return the picked number. To play optimally you must minimize the number of API calls — and the only way to do that on a totally unstructured search space of n integers is binary search.
Maintain a current interval [lo, hi] known to contain the picked value, starting from [1, n]. On each step compute mid = lo + (hi - lo) / 2 and read guess(mid). If the API returns 0, return mid. If it returns 1, the true value is greater than mid, so move lo = mid + 1. If it returns -1, the true value is less, so hi = mid - 1. Termination is guaranteed because the interval shrinks by at least one each round.
The overflow caveat from problems like First Bad Version applies: n may be close to 2^31 - 1, so use the subtraction form of the midpoint. The whole search uses O(log n) calls to guess and O(1) extra memory, which is the information-theoretic optimum.
Examples
n = 10, pick = 66n = 1, pick = 11n = 2, pick = 11Constraints
- 1 <= n <= 2^31 - 1
- 1 <= pick <= n
- The guess API returns -1, 1, or 0.
- Use the subtraction form for mid to avoid overflow when n is near INT_MAX.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.