Guess Number Higher or Lower

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 1 to n
• Pick the middle value

• Use the API result to decide:

  • Search left half
  • Or search right half

Approach

1. Initialize:

• low = 1
• high = n

1. While low <= high:

• Find middle: mid = (low + high) // 2
• Call guess(mid)

1. Based on result:

• 0 → return mid
• -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.