Guess the Number Higher or Lower

Problem Statement

We are playing a Guess Game.

A number is picked between 1 and n.
You must guess the number.
Each time you guess wrong, you are told whether:
Your guess is higher
Your guess is lower
Or equal

You are given a predefined API:

int guess(int num)

It returns:

-1 → Your guess is higher than the picked number
1 → Your guess is lower than the picked number
0 → Your guess is correct

You must return the picked number.

Example 1

Input:

n = 10
pick = 6

Output:

6
Example 2

Input:

n = 1
pick = 1

Output:

1
Constraints
1 <= n <= 2^31 - 1
1 <= pick <= n
Efficient Approach – Binary Search

Since:

The number is between 1 and n
We are told whether our guess is higher or lower

This is a classic Binary Search problem.

Binary Search reduces the search space by half each time.

Why Binary Search?

If we check numbers sequentially:

Worst case → O(n)

Using Binary Search:

Worst case → O(log n)

This is much more efficient, especially since n can be very large (up to 2³¹ − 1).

Step-by-Step Logic
Initialize:
left = 1
right = n
While left <= right:

Find middle:

mid = left + (right - left) // 2
Call guess(mid)
If result == 0 → return mid
If result == -1 → number is smaller → move right = mid - 1
If result == 1 → number is larger → move left = mid + 1
Implementation (Python)
class Solution:
def guessNumber(self, n):
left = 1
right = n

    while left <= right:
        mid = left + (right - left) // 2
        result = guess(mid)

        if result == 0:
            return mid
        elif result == -1:
            right = mid - 1
        else:
            left = mid + 1

Why Use This Formula for Mid?

Instead of:

mid = (left + right) // 2

We use:

mid = left + (right - left) // 2

This prevents integer overflow in some programming languages when n is very large.

Time and Space Complexity

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

Dry Run Example

For:

n = 10
pick = 6
left = 1, right = 10
mid = 5 → guess(5) = 1 (too low)
left = 6
mid = 8 → guess(8) = -1 (too high)
right = 7
mid = 6 → guess(6) = 0

Return 6.