Introduction
This problem is a classic example of using Binary Search to efficiently find a value within a given range.
Instead of checking every number one by one, we reduce the search space by half at each step.
Problem Statement
We are given a number between 1 and n. We need to guess the number using an API:
guess(num)
The API returns:
-1→ Your guess is higher than the number
1→ Your guess is lower than the number
0→ Your guess is correct
Our task is to find the correct number.
Example 1:
Input:
n = 10, pick = 6
Output:
6
Key Idea
Instead of guessing randomly, we use Binary Search:
- Start with the range
1ton
- Pick the middle value
Use the API result to decide:
- Search left half
- Or search right half
Approach
- Initialize:
low = 1high = n
- While
low <= high:
- Find middle:
mid = (low + high) // 2
- Call
guess(mid)
- Based on result:
0→ returnmid
-1→ search left (high = mid - 1)
1→ search right (low = mid + 1)
Python Implementation
# The guess API is already defined
# def guess(num): ...
def guessNumber(n):
low = 1
high = n
while low <= high:
mid = (low + high) // 2
result = guess(mid)
if result == 0:
return mid
elif result == -1:
high = mid - 1
else:
low = mid + 1
Step-by-Step Example
For:
n = 10, pick = 6
- mid = 5 → too low → go right
- mid = 8 → too high → go left
- mid = 6 → correct
Answer: 6
Why Binary Search Works Here
- The range is sorted (1 to n)
- Each guess eliminates half of the possibilities
- Much faster than linear search
Key Points
Always use binary search when:
- Data is sorted
- You need to minimize operations
Reduces time significantly
Very common interview concept
Conclusion
The Guess Number problem is a perfect example of how Binary Search can optimize searching. Instead of checking every number, we intelligently narrow down the range, making the solution highly efficient.
Mastering this concept is essential for solving many advanced problems involving searching and optimization.