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.
猜数字，返回-1，往更小的猜，返回1往更大的猜
int mid = (left+right)>>1 会溢出
C++（3ms）：
1 // Forward declaration of guess API. 2 // @param num, your guess 3 // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 4 int guess(int num); 5 6 class Solution { 7 public: 8 int guessNumber(int n) { 9 int left = 1 ; 10 int right = n ; 11 while(left <= right){ 12 int mid = (right - left)/2 + left ; 13 if (guess(mid) == 0){ 14 return mid ; 15 }else if (guess(mid) == 1){ 16 left = mid+1 ; 17 }else if (guess(mid) == -1){ 18 right = mid-1 ; 19 } 20 } 21 return 0 ; 22 } 23 };