Guess Number Higher or Lower – CA16

My Thinking and Approach

Introduction

In this problem, I was asked to guess a number chosen between 1 and n. After each guess, I get feedback from an API telling me whether my guess is too high, too low, or correct.

At first, it looked like a simple guessing game, but the goal was to minimize the number of guesses, which made me think about optimization.

---

Problem Understanding

• I need to guess a number between 1 and n

• There is an API guess(num):

  • Returns -1 → my guess is too high
  • Returns 1 → my guess is too low
  • Returns 0 → correct guess

• I must return the correct number

---

My Initial Thought

At first, I thought:

• Start from 1
• Keep increasing until I find the number

But this would take O(n) time in the worst case, which is not efficient.

---

Optimized Thinking (Binary Search)

Then I realized:

• The range is sorted (1 to n)
• After each guess, I get direction (higher or lower)

This is exactly where Binary Search can be used.

---

My Approach

• Use two pointers:

  • low = 1
  • high = n

Steps:

1. Find middle:
   mid = low + (high - low) / 2

2. Call API:

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

1. Repeat until the number is found

---

Code (Java)

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 res = guess(mid);

            if (res == 0) {
                return mid;
            } else if (res == -1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }
}

---

Example Walkthrough

Example

Input:
n = 10, pick = 6

Steps:

• mid = 5 → guess(5) = 1 → too low → search right
• mid = 8 → guess(8) = -1 → too high → search left
• mid = 6 → guess(6) = 0 → correct

Output:
6

---

Complexity Analysis

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

---

Key Takeaways

• Binary Search is useful when:

  • Data is sorted
  • We get directional feedback

• Avoid linear search when optimization is possible

---

Conclusion

This problem helped me understand how to apply binary search in a practical scenario. It improved my thinking in reducing time complexity and using feedback efficiently to narrow down the search space.