Guess Number Higher or Lower

How it works

Ternary search divides the search space into three parts instead of two. We pick two midpoints and use the guess API on both. Based on the results, we can eliminate either one-third or two-thirds of the search space. While this approach works, it does not improve on binary search for this problem since we need more API calls per iteration.

Steps

1. Initialize two pointers: l = 1 and r = n.
2. Calculate two midpoints: m1 = l + (r - l) / 3 and m2 = r - (r - l) / 3.
3. Check guess(m1) and guess(m2):
   • If either returns 0, return that midpoint.
   • If both results sum to 0 (one is 1, other is -1), the answer lies between m1 and m2; update both bounds.
   • If guess(m1) is -1, the answer is below m1; set r = m1 - 1.
   • Otherwise, the answer is above m2; set l = m2 + 1.
4. Repeat until the number is found.

Complexity

• Time complexity: O(log_3 n)
• Space complexity: O(1)

Things to watch for

Misinterpreting the guess() API Return Values

The guess() API returns -1 when your guess is higher than the picked number and 1 when your guess is lower. This is counterintuitive since many people expect positive to mean "go higher." Mixing up these return values causes the binary search to move in the wrong direction, leading to infinite loops or incorrect results.

Integer Overflow When Computing the Midpoint

Calculating the midpoint as (l + r) / 2 can cause integer overflow when l and r are both large values close to the maximum integer. The safe approach is to use l + (r - l) / 2, which avoids adding two large numbers together and prevents overflow in languages with fixed-size integers like Java, C++, and Go.

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 1, n
        while True:
            m1 = l + (r - l) // 3
            m2 = r - (r - l) // 3
            if guess(m1) == 0:
                return m1
            if guess(m2) == 0:
                return m2
            if guess(m1) + guess(m2) == 0:
                l = m1 + 1
                r = m2 - 1
            elif guess(m1) == -1:
                r = m1 - 1
            else:
                l = m2 + 1

/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        while (true) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            if (guess(m1) == 0) return m1;
            if (guess(m2) == 0) return m2;
            if (guess(m1) + guess(m2) == 0) {
                l = m1 + 1;
                r = m2 - 1;
            } else if (guess(m1) == -1) {
                r = m1 - 1;
            } else {
                l = m2 + 1;
            }
        }
    }
};