GUESS NUMBER HIGHER OR LOWER

 

Guess Number Higher or Lower – Binary Search Approach

Introduction

In this problem, we are playing a guessing game where we need to find a number chosen between 1 and n. We are given an API guess(num) that helps us determine whether our guess is too high, too low, or correct.

This problem is a classic example of using Binary Search to efficiently find the answer.

Problem Statement

• A number is picked between 1 and n

• We need to guess the number using the API:

  • -1 = guess is too high

  • 1 = guess is too low

  • 0 = correct guess

Return the picked number.

Example

Input:

n = 10, pick = 6

Output:

6

Solution Code

public class Solution extends GuessGame {
    public int guessNumber(int n) {
          
        int l = 1;
        int r = n;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            int ans = guess(mid);

            if (ans == 0) {
                return mid;
            }
            else if (ans == -1) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }

        return 0;
    }
}

Approach Used: Binary Search

Idea

Instead of checking every number one by one, we repeatedly divide the search space into halves.

How It Works

1. Initialize:

   • l = 1, r = n

2. Find middle:

   • mid = l + (r - l) / 2

3. Call guess(mid):

   • If 0 = correct answer

   • If -1 = number is smaller = search left half

   • If 1 = number is larger = search right half

4. Repeat until the number is found

Why This Approach Was Chosen

• Reduces search space by half each time

• Much faster than linear search

• Efficient for large values of n

Alternative Approach

• Linear Search

  for(int i = 1; i <= n; i++)
  

   Time Complexity: O(n)

Why not used?
Too slow for large inputs (n can be up to 2³¹ - 1)

Time and Space Complexity

• Time Complexity: O(log n)

• Space Complexity: O(1)

Important Observation

• mid = l + (r - l) / 2 is used to avoid overflow

• The search range reduces after every guess

Edge Cases

• n = 1 = only one possible answer

• Pick is at the boundaries (1 or n)

• Large values of n

Conclusion

Binary Search is the most efficient way to solve this problem. By repeatedly narrowing down the search space, we quickly arrive at the correct answer with minimal guesses. This approach is widely used in problems involving sorted or bounded ranges.