ASSIGNMENT 16

1. Guess Number higher or lower

Problem

You are playing a guessing game:
• A number is picked between 1 and n
• You have to guess that number

You are given an API guess(num) that returns:
• -1 → your guess is too high
• 1 → your guess is too low
• 0 → correct guess 

Your task is to find the correct number.

Example

Input:
n = 10, picked number = 6

Output:
6 

Approach Used

Binary Search (Optimal Approach)

Key Idea:
• The number lies in a sorted range from 1 to n
• After each guess, we get direction (higher/lower)

This is exactly what binary search is designed for
• Reduce search space by half each time

Step-by-Step Explanation

Step 1: Define Search Range

Start with:
• Left boundary = 1
• Right boundary = n

This is the range where the number exists

Step 2: Find Middle Value

Pick the middle number of the current range

This is your guess

Step 3: Use the Guess API

Check the result of your guess:
• If result is 0 → correct number found
• If result is 1 → guessed number is too small
• If result is -1 → guessed number is too large 

Step 4: Reduce Search Space

Based on the result:
• If guess is too small → search in right half
• If guess is too large → search in left half

This eliminates half of the possible numbers

Step 5: Repeat Process

Continue:
• Find middle
• Check using API
• Reduce range

Until the correct number is found

CODE:

class Solution(object):
def guessNumber(self, n):
left, right = 1, 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

Complexity Analysis

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

Conclusion

The problem is a direct application of binary search on a fixed range. Instead of searching blindly, we use feedback from the API to eliminate half of the possibilities at every step.