Guess the Number Higher or Lower [Leetcode]

#algorithms #python #computerscience #interview

Guess Number Higher or Lower

Problem

You’re playing a game where a number is picked between 1 and n.
You have to guess it using an API that tells you:

-1 → your guess is too high
1 → your guess is too low
0 → correct guess

Strategy

This is basically a classic binary search problem.

Instead of searching an array, you’re searching a range from 1 to n.

At each step:

Pick the middle number
Use the API to check
Narrow the range based on the response

Code

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

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

            if res == 0:
                return mid
            elif res == -1:
                right = mid - 1
            else:
                left = mid + 1

Key Lines Explained

mid = (left + right) // 2
Choose the middle of the current range.
res = guess(mid)
Ask whether the guess is correct, too high, or too low.
res == -1
Means the guess is too high → move left.
res == 1
Means the guess is too low → move right.

Why This Works

Each guess eliminates half of the remaining range.

So instead of checking every number, we quickly narrow it down using the feedback.

Complexity

Time: O(log n)
Space: O(1)

Final Note

This problem is a direct application of binary search.

The only difference is that instead of comparing values in an array, you’re using feedback from the API to guide your search.

DEV Community