Guess Number Higher or Lower Using Binary Search in Python

Problem Explanation

We are playing a game where a number is picked between 1 and n.
Your task is to guess the correct number.

You are given an API:

• guess(num) returns:

  • -1 → your guess is too high
  • 1 → your guess is too low
  • 0 → correct guess

Your goal is to find the picked number efficiently.

Example:

• Input: n = 10, pick = 6
  Output: 6

• Input: n = 1, pick = 1
  Output: 1

---

Method Used: Binary Search

Idea

Instead of guessing randomly, we:

• Start from the middle
• Eliminate half of the range each time
• Narrow down to the correct number

---

Why This Method?

• Time complexity: O(log n)
• Much faster than linear search (O(n))
• Efficient for large values of n

---

Python Code with Explanation

class Solution:
    def guessNumber(self, n):

Defines the function.

---

        left = 1
        right = n

We set the search range from 1 to n.

---

        while left <= right:

Continue searching while the range is valid.

---

            mid = (left + right) // 2

Find the middle number.

---

            result = guess(mid)

Call the given API with our guess.

---

            if result == 0:
                return mid

If result is 0, we found the correct number.

---

            elif result == -1:
                right = mid - 1

If guess is too high, search in the left half.

---

            else:
                left = mid + 1

If guess is too low, search in the right half.

---

Complete Code

class Solution:
    def guessNumber(self, n):
        left = 1
        right = n

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

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

---

Step-by-Step Example

Input:

n = 10, pick = 6

Steps:

• Guess 5 → too low
• Guess 8 → too high
• Guess 6 → correct

Output:

6

---

Key Takeaway

Binary Search helps reduce the search space efficiently, making it the best approach for this problem.

---