Guess Number Higher or Lower

Problem Statement

We are playing the Guess Game:
I pick a number from 1 to n.
You have to guess the number I picked.
Each time you guess wrong, I tell you if my number is higher or lower than your guess.

You can call a pre-defined API:

int guess(int num)

It returns:

-1 if your guess is higher than the number (i.e., num > pick)
1 if your guess is lower than the number (i.e., num < pick)
0 if your guess is correct (i.e., num == pick)

Your task is to return the number I picked.

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Constraints:

1 <= n <= 2^31 - 1
1 <= pick <= n

Approach: Binary Search

The most efficient way to guess the number is using binary search. Since the API tells us whether the pick is higher or lower, we can halve the search space with each guess.

Steps:

Start with a range [1, n].
Guess the middle number mid = left + (right - left) // 2.
Call guess(mid):
If it returns 0, we found the number.
If it returns -1, the pick is lower, so move right = mid - 1.
If it returns 1, the pick is higher, so move left = mid + 1.
Repeat until the correct number is found.
Python Solution

The guess API is already defined for you.

def guess(num: int) -> int:

Python Code

class Solution:
def guessNumber(self, n: int) -> int:
left, right = 1, n

    while left <= right:
        mid = left + (right - left) // 2
        res = guess(mid)

        if res == 0:
            return mid      # Correct guess
        elif res < 0:
            right = mid - 1 # Pick is lower than mid
        else:
            left = mid + 1  # Pick is higher than mid

Time Complexity: O(log n) — the search space is halved each step.
Space Complexity: O(1) — only a few pointers are used.

This method is concise, efficient, and ideal for very large numbers within the constraints. It’s a classic example of binary search in real-world guessing problems.