LeetCode題目鏈接

注意：凡是以英文出現(xiàn)的，都是題目提供的，包括答案代碼里的前幾行。

題目：

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'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

希望看到這里的同學(xué)能夠先思考，最好是能夠自己寫具體的實(shí)現(xiàn)，有更好的答案可以直接在下面評(píng)論。

答案：

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

// 這里說明一下，上面的幾行代碼是題目提供的

class Solution {
public:
    int guessNumber(int n) {
        int begin = 0;
        int end = n;
        int num, res;
        while (begin <= end) {
            num = (end - begin)/2 + begin;  // 注意：這里不能用num = (end + begin)/2
            res = guess(num);
            if (res == 0) {
                return num;
            }
            else if (res == 1) {
                begin = num + 1;
            }
            else {
                end = num - 1;
            }
        }
        return 0;
    }
};

解析：

不能用 num = (end + begin) / 2，是因?yàn)椴皇撬械臏y(cè)試都能通過，這里需要考慮數(shù)字過大導(dǎo)致的溢出，如果給出的數(shù)字num很大，那么 end + begin超出int類型的范圍。