Guess the number higher or lower

Problem

You are given a number n. There is a hidden number between 1 and n, and you need to guess it.

You are provided with an API:

guess(num)

It returns:

0 → if your guess is correct
1 → if the hidden number is higher
-1 → if the hidden number is lower

Code
class Solution:
    def guessNumber(self, n: int) -> int:
        l = 1
        r = n
        while l <= r:
            mid = (r + l) // 2
            if guess(mid) == 0:
                return mid
            elif guess(mid) == 1:
                l = mid + 1
            else:
                r = mid - 1

Step-by-Step Explanation

1. Initialize Search Range l=1 r=n

The number lies between 1 and n, so we start with the full range.

2. Use Binary Search Loop
while l <= r:
We continue searching while the range is valid.

3. Find the Middle
mid = (r + l) // 2
We take the middle of the current range to reduce the search space by half each time.

4. Call the Guess API
if guess(mid) == 0:
return mid
If the guess is correct, we return the answer immediately.

5. Adjust Search Range
Case 1: Hidden number is higher
elif guess(mid) == 1:
l = mid + 1

If the result is 1, the target number is greater than mid.
So we ignore the left half and search in the right half.

Case 2: Hidden number is lower
else:
r = mid - 1

If the result is -1, the target number is smaller than mid.
So we ignore the right half and search in the left half.

Key Idea
This is a classic binary search problem where each guess eliminates half of the remaining numbers.

Time Complexity
O(log n) because the search space is halved in every iteration.

Space Complexity
O(1) because only a few variables are used.

*Why This Approach is Efficient
*
Instead of checking every number one by one, binary search quickly narrows down the possible values. This makes it much faster, especially for large n.