💬 Discord
Sign In
NeetCode #262LC-374EasyBinary SearchNC 250
← Back to All Problems

#262 · #374 · Guess Number Higher or Lower(猜数字大小)

📌 Problem Statement & Constraints

This is an interactive problem. A number is picked from 1 to n. You call guess(num) which returns -1 if your guess is higher, 1 if it is lower, and 0 if correct. Return the picked number. Constraints: 1 <= n <= 2^31 - 1; at most 30 guesses.

💡 Core Algorithmic Approaches

  1. Plain binary search over [1, n].
  2. guess(mid) == 0 means found; -1 means the guess is too high, so shrink the upper bound; 1 means too low, so raise the lower bound.
  3. With n up to 2^31, at most 31 iterations are needed, well within the 30-guess budget (the exact count is ceil(log2(n+1))).
  4. Keep the inclusive-bounds formulation, since the value space is a closed interval.

💻 Benchmark Python3 Implementation

class Solution:
    def guessNumber(self, n: int) -> int:
        lo, hi = 1, n
        while lo <= hi:
            mid = (lo + hi) // 2
            r = guess(mid)
            if r == 0:
                return mid
            if r < 0:                  # mid is too high
                hi = mid - 1
            else:                      # mid is too low
                lo = mid + 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): about 31 iterations for the maximum n.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Inverting the meaning of the return value: -1 means the guess is too high, so the upper bound must decrease. Getting this backwards sends the search the wrong way.
  • Using a linear scan: O(n) with n up to 2^31.
  • Off-by-one on the initial range: the valid range is [1, n] inclusive, not [0, n).
  • Ignoring the guess budget: binary search uses ceil(log2(n+1)) <= 31 calls, which fits the limit.