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:
Input: n = 10, pick = 6
Output: 6
典型的二分法结题思路哈，就不用分析了吧。
- 求中位数禁止用（left + right）/ 2 , 而应该用 left + (right - left) / 2 从而可以避免溢出
- 外部调用函数尽量越少用越好
// 解法一
int guess(int num) {
int n = 31;
if (num == n)
return 0;
else if (num < n)
return 1;
else
return -1;
}
class SolutionGuess {
public:
int guessNumber(int n) {
int left = 1, right = n, mid = (1 + n) / 2;
while(guess(mid) != 0) {
if (guess(mid) < 0)
right = mid - 1;
else
left = mid + 1;
mid = (left + right) / 2;
}
return mid;
}
};// 解法二
int guess(int num);
class Solution {
public:
int guessNumber(int n) {
int judge, mid, left = 1, right = n;
while(true) {
mid = left + (right - left)/2;
judge = guess(mid);
if (judge == 0)
return mid;
else if (judge < 0)
right = mid - 1;
else
left = mid + 1;
}
}
};