CA 16 - [Leetcode] Guess the Number Higher or Lower

Problem

We are playing a game where a number is picked from 1 to n.

You need to guess the number using a predefined API guess(num):

Returns -1 if your guess is higher than the picked number
Returns 1 if your guess is lower than the picked number
Returns 0 if your guess is correct

The task is to return the picked number.

Output

Example 1
Output: 6
Example 2
Output: 1
Example 3
Output: 1

My Approach

To solve this problem, I used Binary Search.

I set two pointers:

left = 1
right = n

Then I repeatedly calculate the middle value:

If guess(mid) == 0, I return mid
If guess(mid) == -1, I move to the left half
If guess(mid) == 1, I move to the right half

I continue this process until I find the correct number.

This works because the search space is reduced by half in every step.

This approach is efficient because:

It reduces the search space logarithmically
It requires only constant extra space
Code

class Solution(object):
    def guessNumber(self, n):
        left = 1
        right = n
        while left <= right:
            mid = (left + right) // 2
            result = guess(mid)
            if result == 0:
                return mid
            elif result == -1:
                right = mid - 1
            else:
                left = mid + 1