374. Guess Number Higher or Lower Easy

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

• -1: Your guess is higher than the number I picked (i.e. num > pick).
• 1: Your guess is lower than the number I picked (i.e. num < pick).
• 0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

Example 1:
Input: n = 10, pick = 6
Output: 6

Example 2:
Input: n = 1, pick = 1
Output: 1

Example 3:
Input: n = 2, pick = 1
Output: 1

Approach

Input: A number n, and a predefined function guess.

Output: Return the picked number.

This problem belongs to the Basic Search category, suitable for using binary search to quickly locate the target value in an ordered sequence.

Through binary search, we find the median mid in [0, n] and use guess to determine if the picked number is to the left or right.

If guess returns 0, we guessed correctly.

If guess returns 1, it means our guess is lower than the picked number, so we need to search the right half, updating the left boundary.

If guess returns -1, it means our guess is higher than the picked number, so we need to search the left half, updating the right boundary.

Note: In the implementation, if guess(mid) == 1, it means we should guess higher, so the target is to the right.

Implementation

python

class Solution:
    def guessNumber(self, n: int) -> int:
        # Define the left and right boundaries for binary search
        l, h = 0, n

        # Continue searching while left boundary <= right boundary
        while l <= h:
            # Take the midpoint
            mid = (l + h) // 2

            # Call the API guess(mid)
            # guess(mid) == 0 means guessed correctly
            if guess(mid) == 0:
                return mid
            
            # guess(mid) == 1 means pick is higher than mid, we should search to the right
            if guess(mid) == 1:
                l = mid + 1
            else:
                # Otherwise (guess(mid) == -1), pick is lower than mid, search to the left
                h = mid - 1

javascript

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let low = 0;
    let high = n;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (guess(mid) === 0) return mid;

        if (guess(mid) === 1) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
};

Complexity Analysis

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

Links

374. Guess Number Higher or Lower (English)

374. 猜数字大小 (Chinese)