LeetCode //C – 374. Guess Number Higher or Lower

本文介绍: 【代码】LeetCode //C – 374. Guess Number Higher or Lower。

374. Guess Number Higher or Lower

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

Constraints:

$2^{31} – 1 1<=n<=231−1$

From: LeetCode
Link: 374. Guess Number Higher or Lower

Solution:

Ideas：

We initialize two pointers, left and right, to the beginning and end of the range, respectively.
We perform a binary search by repeatedly choosing the middle element of the current range as our guess.
We call the guess API with our current guess. If the return value is 0, we have found the correct number and return it. If the return value is -1, our guess is too high, so we adjust the right boundary. If the return value is 1, our guess is too low, so we adjust the left boundary.
This process continues until we find the correct number.

Code:

/** 
 * 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);

int guessNumber(int n) {
    long long left = 1, right = n;
    while (left <= right) {
        // Use long long for mid to avoid integer overflow
        long long mid = left + (right - left) / 2;
        int res = guess(mid);
        if (res == 0) {
            // The guess is correct
            return mid;
        } else if (res < 0) {
            // The picked number is lower than our guess
            right = mid - 1;
        } else {
            // The picked number is higher than our guess
            left = mid + 1;
        }
    }
    // This line should never be reached if the API behaves as expected
    return -1;
}