CA 16 -Guess the Number Higher or Lower

Problem
Guess the Number Higher or Lower
We are playing a guessing game.

A number is picked between 1 and n, and your task is to find that number using a provided API:

guess(num) returns:

• -1 → your guess is higher
• 1 → your guess is lower
• 0 → your guess is correct

You need to return the number that was picked.

• Input: n = 10, pick = 6 → Output: 6
• Input: n = 1, pick = 1 → Output: 1
• Input: n = 2, pick = 1 → Output: 1

Approach

This problem is a perfect fit for Binary Search.

Instead of guessing randomly, we narrow down the search space efficiently.

Steps:

• Start with a range from 1 to n
• Find the middle value
• Use the guess() API:
• If result is 0, we found the answer
• If result is -1, search in the left half
• If result is 1, search in the right half
• Repeat until the number is found

This reduces the search space by half each time.

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

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