# 🎯 Guess the Number Game (Java) – Binary Search Made Simple

Imagine playing a game where you have to guess a number chosen by someone within a range from 1 to n. After each guess, you’re told whether your guess is too high, too low, or correct.

Sounds simple, right? But solving it efficiently is where the real challenge lies.

In this blog, we’ll break down how to solve this problem using one of the most powerful techniques in computer science: Binary Search.

---

🚀 Problem Statement

You are playing the Guess Game:

• A number is picked between 1 and n
• You must guess it
• After each guess, you get feedback via an API:

🔧 API Behavior

```java id="x3k2op"
int guess(int num)

Returns:

* `-1` → Your guess is **too high**
* `1` → Your guess is **too low**
* `0` → 🎉 Correct guess!

---

## 🤔 Why Not Use Linear Search?

You could start from `1` and keep guessing:



```text id="mnb82x"
1 → 2 → 3 → 4 → ...

But this would take O(n) time in the worst case.

👉 That’s inefficient for large values of n.

---

💡 Key Insight: Use Binary Search

Since the number lies in a sorted range (1 to n), we can apply binary search to drastically reduce guesses.

🧠 Strategy:

• Always guess the middle number
• Use the response to eliminate half of the search space

---

⚡ Step-by-Step Approach

1. Initialize:

• low = 1
• high = n

1. Repeat until found:

• Compute mid
• Call guess(mid)

1. Adjust range:

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

---

🧑‍💻 Java Implementation

```java id="jz9kq1"
// The guess API is defined in the parent class GuessGame
// int guess(int num);

public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1;
int high = n;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int result = guess(mid);

        if (result == 0) {
            return mid; // correct guess
        } else if (result == -1) {
            high = mid - 1; // too high
        } else {
            low = mid + 1; // too low
        }
    }

    return -1; // fallback (should not happen)
}

}

---

## 🔍 Example Walkthrough

Let’s say:



```text id="g4l0xp"
n = 10, picked number = 6

Step	Guess	Feedback	New Range
1	5	Too low	[6, 10]
2	8	Too high	[6, 7]
3	6	Correct	✅ Found

---

⏱️ Complexity Analysis

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

✔ Each step cuts the search space in half

---

⚠️ Common Mistakes

• ❌ Using (low + high) / 2 → may cause integer overflow
• ❌ Not updating low or high correctly
• ❌ Forgetting that guess() is already defined

---

🎯 Why This Problem Matters

This is more than just a guessing game—it teaches:

• Efficient searching
• Decision making using feedback
• Real-world use of binary search

---

🏁 Conclusion

The Guess Game is a perfect example of how a simple problem can be optimized using the right approach.

Instead of guessing blindly, binary search allows you to:

• Think strategically
• Minimize attempts
• Achieve optimal performance