🎯 Guess Number Higher or Lower (Binary Search Explained)

This problem is a classic example of Binary Search, one of the most important algorithms in programming and interviews.

---

📌 Problem Statement

You need to guess a number between 1 and n.

A predefined API is available:

• guess(num) = -1 → your guess is too high
• guess(num) = 1 → your guess is too low
• guess(num) = 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

Instead of guessing randomly, we can eliminate half of the search space each time.

👉 This is exactly what Binary Search does.

---

🔄 Approach (Binary Search)

Step-by-Step:

1. Set:

• low = 1
• high = n

1. While low <= high:

• Find middle: mid = (low + high) // 2
• Call guess(mid)

1. Based on result:

• If 0 → return mid
• If -1 → search left (high = mid - 1)
• If 1 → search right (low = mid + 1)

---

💻 Python Code

```python id="g1"

The guess API is predefined

def guess(num): ...

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

---

🧾 Dry Run

For: n = 10, pick = 6

* low = 1, high = 10 → mid = 5 → guess = 1 (too low)
* low = 6, high = 10 → mid = 8 → guess = -1 (too high)
* low = 6, high = 7 → mid = 6 → guess = 0

👉 Answer = 6

---

⚡ Complexity

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

---

🔥 Why This Works

* Each step reduces search space by half
* Very efficient for large inputs
* Standard binary search pattern

---

⚠️ Edge Cases

* n = 1
* pick at boundaries (1 or n)
* large values of n

---

🏁 Conclusion

This problem is a direct application of Binary Search and teaches:

* Efficient searching
* Decision-based narrowing
* Logarithmic optimization

Mastering this helps solve many similar problems.