Guess Number Higher or Lower (Binary Search)

Guess Number Higher or Lower (Binary Search)
Problem Statement

We are playing a guessing game:

A number is picked between 1 and n

We must guess the number

We are given an API:

Return Meaning
-1 Guess is too high
1 Guess is too low
0 Correct guess

We need to find the picked number.

Examples
Input: n = 10, pick = 6
Output: 6

Input: n = 1, pick = 1
Output: 1
Approach 1: Linear Search (Not Efficient)
Idea

Start guessing from 1 to n until we find the number.

Problem

This takes O(n) time which is very slow for large n (n can be very big).

So we need a better approach.

Approach 2: Binary Search (Best Method)
Idea

Binary Search works because:

The number is between 1 and n

We can eliminate half the numbers each time

Steps

Start with low = 1, high = n

Find middle number

Call guess(mid)

If result:

0 → Found number

-1 → Number is smaller → move left

1 → Number is larger → move right

Repeat until found

Python Code
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

Example Walkthrough

For:

n = 10
pick = 6
Low High Mid Result
1 10 5 Low
6 10 8 High
6 7 6 Correct

Answer = 6

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

Binary search is very fast because it reduces the search space by half each time.

Linear vs Binary Search
Method Time Complexity
Linear Search O(n)
Binary Search O(log n)

Binary search is much faster.

Conclusion

This problem is a classic example of Binary Search.

Key concepts learned:

Binary search

Search space reduction

Efficient searching

Divide and conquer approach

Binary search is one of the most important algorithms in programming and interviews.