LeetCode*374. Guess Number Highe

LeetCode题目链接

注意：凡是以英文出现的，都是题目提供的，包括答案代码里的前几行。

题目：

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.

希望看到这里的同学能够先思考，最好是能够自己写具体的实现，有更好的答案可以直接在下面评论。

答案：

// 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，是因为不是所有的测试都能通过，这里需要考虑数字过大导致的溢出，如果给出的数字num很大，那么 end + begin超出int类型的范围。