Guess Number Higher or Lower

Problem

Hidden pick is between 1 and n. guess(x) returns 0 if correct, -1 if pick < x, 1 if pick > x. Return the pick.

Constraints

• 1 ≤ n ≤ 2³¹−1
• 1 ≤ pick ≤ n

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def guessNumber(self, n):
        lo, hi = 1, n
        while lo <= hi:
            mid = (lo + hi) // 2
            g = guess(mid)
            if g == 0:
                return mid
            elif g < 0:
                hi = mid - 1
            else:
                lo = mid + 1
        return -1

Java

class Solution {
    int pick;
    int guess(int x) { if (x == pick) return 0; return x < pick ? 1 : -1; }
    public int guessNumber(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            int g = guess(m);
            if (g == 0) return m;
            if (g > 0)  lo = m + 1;
            else        hi = m - 1;
        }
        return lo;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.