Guess Number Higher or Lower - CA16

My Thinking and Approach

---

Introduction

In this problem, I was given a number range from 1 to n and asked to guess a number picked within this range.

I can use a given API to check whether my guess is higher, lower, or equal to the picked number.

---

Problem Statement

• A number is picked between 1 and n

• Use API guess(num):

  • Returns -1 → guess is higher
  • Returns 1 → guess is lower
  • Returns 0 → correct guess

• Find and return the picked number

---

My Initial Thought

At first, I considered:

• Checking each number one by one

But this approach is slow for large values of n.

---

Key Observation

Instead of checking all numbers:

• I can reduce the search space
• Based on API response, eliminate half of the range

---

Optimized Approach

I decided to use Binary Search.

Logic:

• If guess is too high → search left half
• If guess is too low → search right half
• Continue until correct number is found

---

My Approach (Step-by-Step)

1. Initialize:

• left = 1

• right = n

  1. While left <= right:

• Find mid = (left + right) // 2

• Call guess(mid):

  • If result == 0 → return mid
  • If result == -1 → move right = mid - 1
  • If result == 1 → move left = mid + 1

---

Code (Python)

Below is the implementation clearly separated inside a code block:

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

---

Example Walkthrough

Input:

n = 10, pick = 6

Steps:

• mid = 5 → guess is low
• move right → search [6, 10]
• mid = 8 → guess is high
• move left → search [6, 7]
• mid = 6 → correct

Output:

6

---

Complexity Analysis

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

---

Key Takeaways

• Binary search reduces search space efficiently
• Avoid linear search for large inputs
• Divide and conquer approach is useful

---

Conclusion

This problem helped me understand how binary search can be used effectively to minimize the number of guesses.

---