374. Guess Number Higher or Lower

我不是女神ヾ 2022-06-06 22:35 208阅读 0赞

题目要求：

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. -1 : My number is lower
  2.  1 : My number is higher
  3.  0 : Congrats! You got it!

Example: 

  1. n = 10, I pick 6.
  3. Return 6.

思路详解：

二分查找，重点是mid = low+(high-low)/2；如果用mid = (low+high)/2 容易溢出。

答案详解：

// 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 low = 1,high = n;
int mid;
while(low<=high)
{
mid = (high-low)/2+low;
if(guess(mid)==0)
return mid;
else if(guess(mid)>0)
low = mid + 1;
else
high = mid -1;
}
}
};

发表评论

表情：
评论列表 （有 0 条评论，208人围观）

还没有评论，来说两句吧...

相关阅读