How do you solve Guess Number Higher or Lower?

Implement a binary search with two pointers, left and right, initialized to 1 and n. In each iteration, guess the midpoint. If the guess is correct, return it. If the guess is higher than the target, move the right pointer to mid - 1. If the guess is lower, move the left pointer to mid + 1. Continue until the correct number is found.

Guess Number Higher or Lower

Q: What is the time complexity of Guess Number Higher or Lower?

O(log n). Each guess halves the search space, so the number of guesses needed is proportional to the logarithm base 2 of n.

Q: What pattern does Guess Number Higher or Lower use?

The Pattern: Binary Search (Feedback-Guided Search) The Heuristic: When searching for a target in a sorted range with directional feedback, use binary search by halving the search space each iteration based on the feedback to achieve logarithmic time.

Easy Binary Search

Problem

Given an integer n representing the range [1, n], return the number that matches the hidden target by using the guess API which returns -1, 1, or 0 indicating whether the guess is higher, lower, or correct.

1 ≤ n ≤ 2³¹ - 1

Example

Input: n = 10

Output: 6

Suppose the hidden target is 6. The algorithm starts with left=1 and right=10. It guesses mid=5, and guess(5) returns 1 (target is higher). It then moves left to 6. Next, it guesses mid=8, and guess(8) returns -1 (target is lower). It moves right to 7. Then it guesses mid=6, and guess(6) returns 0, indicating the correct number is found and returns 6.

Approach

Straightforward Solution

A naive approach would guess numbers sequentially from 1 to n, which is O(n) and inefficient for large n.

Core Observation

The problem is a classic search for a hidden number within a sorted range, where each guess narrows down the search space based on feedback. The fundamental truth is that the search space can be halved each time by comparing the guess to the target.

Path to Optimal

Preview

Recognizing the problem as a search in a sorted range with feedback indicating direction suggests binary search…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a binary search with two pointers, left and right, initialized to 1 and n. In each iteration, guess the midpoint…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each guess halves the search space, so the number of guesses needed is proportional to the logarithm base 2 of n.

Space

O(1)

Only a fixed number of variables (left, right, mid, result) are used, regardless of input size.

Pattern Spotlight

Binary Search (Feedback-Guided Search)

When searching for a target in a sorted range with directional feedback, use binary search by halving the search space each iteration based on the feedback to achieve logarithmic time.

Solution

Python

1class Solution:
  def guessNumber(self, n: int) -> int:
      left = 1
      right = n
5
      while left <= right:
          mid = (left + right) // 2
          result = guess(mid)
9
          if result == 0:
              return mid
          elif result == -1:
              right = mid - 1
          else:
              left = mid + 1

Step-by-Step Solution

Initialize Search Boundaries to Cover the Entire Range

3left = 1
4right = n

Objective

To set the initial search space boundaries to the full range from 1 to n.

Key Insight

Starting with left at 1 and right at n ensures the entire possible range of the target is considered. This setup is essential for binary search to function correctly, as it defines the initial search interval that will be halved iteratively.

Interview Quick-Check

Core Logic

Setting left=1 and right=n defines the initial search space for the binary search algorithm.

State & Boundaries

The search space is inclusive of both left and right pointers, so the loop condition must consider equality (left <= right).

Iteratively Narrow Search Space Using Midpoint Guesses

To repeatedly guess the midpoint and adjust search boundaries based on feedback until the target is found.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

left = 1

Initialize the left boundary of the search space to 1.

Setting left to 1 ensures the search covers the entire valid range starting from the smallest possible target.

Line 4 Critical

right = n

Initialize the right boundary of the search space to n.

Setting right to n ensures the search covers the entire valid range up to the largest possible target.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does moving the left or right pointer based on the guess API's feedback guarantee finding the target in O(log n) time?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Guess Number Higher or Lower from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Guess Number Higher or Lower drill

or drill a free problem

1	`class Solution:`
2	`def guessNumber(self, n: int) -> int:`
3	`left = 1`
4	`right = n`
5
6	`while left <= right:`
7	`mid = (left + right) // 2`
8	`result = guess(mid)`
9
10	`if result == 0:`
11	`return mid`
12	`elif result == -1:`
13	`right = mid - 1`
14	`else:`
15	`left = mid + 1`