Guess the Number Higher or Lower

Let us first understand the given LeetCode problem “Guess Number Higher or Lower”.

We are given a number n, and we need to guess a number between 1 and n.
There is a predefined function guess(num) which returns:

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

Sample Input and Output
Input:
n = 10, pick = 6

Output:
6

Explanation:
We continuously make guesses, and based on the result returned by the guess() function, we adjust our search range accordingly.

Approach to the Solution

To solve this problem efficiently, the key question is:
“How can we minimize the number of guesses?”

If we check every number sequentially (linear search), it will take more time.
To optimize this, we use Binary Search, which reduces the search space by half in each step.

How It Works

We consider a search range from 1 to n
Find the middle element of the range
Use guess(mid) to decide the next step

*Step-by-Step Execution
*

low = 1, high = 10  
mid = 5 → guess(5) → 1 (picked number is higher)  
→ move right → low = 6  
mid = 8 → guess(8) → -1 (picked number is smaller)  
→ move left → high = 7  
mid = 6 → guess(6) → 0 (correct guess)  
Hence, the answer is 6.

Final Approach

Use two pointers: low and high
Find the middle element mid
Call guess(mid)

Based on the result:
If 0 → return mid
If 1 → search right half (low = mid + 1)
If -1 → search left half (high = mid - 1)

Algorithm

def guessNumber(self, n):
        low = 1
        high = n
        while low <= high:
            mid = (low + high) // 2
            res = guess(mid)

            if res == 0:
                return mid
            elif res == 1:
                low = mid + 1
            else:
                high = mid - 1