Guess the Number Higher or Lower

Introduction

This problem is based on a guessing game where we need to find a hidden number efficiently.

Instead of checking every number one by one, we can use Binary Search, which drastically reduces the number of guesses.

Problem Statement

You are given a number n. A number is picked between 1 and n.

You need to guess the number using the API:

guess(num)

It returns:

• -1 → Your guess is too high
• 1 → Your guess is too low
• 0 → Correct guess

Return the number that was picked.

Examples

Example 1:
Input: n = 10, pick = 6
Output: 6

Example 2:
Input: n = 1, pick = 1
Output: 1

Example 3:
Input: n = 2, pick = 1
Output: 1

Intuition

• If guess is too high → search left
• If guess is too low → search right

This perfectly fits Binary Search

Approach (Binary Search)

Algorithm Steps

• Initialize:

  • low = 1
  • high = n

• While low <= high:

  • Find mid: mid = (low + high) // 2
  • Call guess(mid):
    • If 0 → return mid
    • If -1 → search left → high = mid - 1
    • If 1 → search right → low = mid + 1

Code (Python)

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 Explanation

For n = 10, pick = 6:

• mid = 5 → too low → go right
• mid = 8 → too high → go left
• mid = 6 → correct

Complexity Analysis

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

Conclusion

This problem demonstrates the power of Binary Search, which is one of the most important techniques in programming.