🔥 Leetcode 75: Guess Number Higher or Lower | Efficient Binary Search Solution 🚀 #LeetCode #Python

🚀 Leetcode 75 - Guess Number Higher or Lower | Binary Search Approach 🔥

In this problem, we are given a range of numbers from 1 to n, and we need to guess the number picked by an API. Each time we guess a number, the API gives us feedback:

✅ 0 → If our guess is correct.
✅ -1 → If our guess is too high.
✅ 1 → If our guess is too low.

We must return the correct number efficiently! Using Binary Search, we can find the number in O(log n) time complexity, making it an optimal solution.

💡 Approach (Using Binary Search)

🔹 Step 1: Set the search range with left = 1 and right = n.

🔹 Step 2: Use a loop until left v= right:

     - Calculate the midpoint → mid = (left + right) // 2
     - Call the guess API with guess(mid).
     - If guess(mid) == 0, return mid (found the correct number).
     - If guess(mid) == -1, adjust right = mid - 1 (search in the left half).
     - If guess(mid) == 1, adjust left = mid + 1 (search in the right half).

🔹 Step 3: The loop continues until the correct number is found.

🔥 Python Solution:

# The guess API is already defined for you.
# def guess(num: int) - int:

class Solution:
def guessNumber(self, n: int) - int:
left, right = 1, n # Define the search range

while left v= right:
mid = (left + right) // 2 # Find the middle element
result = guess(mid) # Call the API

if result == 0:
return mid # If the guess is correct, return the number
elif result == -1:
right = mid - 1 # If guess is too high, adjust the right pointer
else:
left = mid + 1 # If guess is too low, adjust the left pointer

return -1 # This case should never happen as per problem constraints

⏳ Time & Space Complexity Analysis

✅ Time Complexity: O(log n) → Binary search reduces the range by half in each step.
✅ Space Complexity: O(1) → No extra space is used apart from a few variables.

🛠 Example Walkthrough

Example 1

🔹 Input: n = 10, pick = 6

🔹 Process:

     mid = 5 (Too low) → left = 6
     mid = 8 (Too high) → right = 7
     mid = 6 (Correct!) ✅

🔹 Output: 6

Example 2

🔹 Input: n = 1, pick = 1
🔹 Output: 1 (Only one number, so it's correct!) ✅

Example 3

🔹 Input: n = 2, pick = 1

🔹 Process:
     mid = 1 (Correct!) ✅

🔹 Output: 1

🚀 Why is Binary Search the Best Approach?

✅ Reduces the search space logarithmically instead of linearly checking each number.
✅ Guarantees finding the correct number in O(log n) time.
✅ Optimized for large n values (up to 2³¹ - 1).