### 题目描述

题目链接：374. Guess Number Higher or Lower

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 will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API

`int guess(int num)`

, which returns 3 possible results:

`-1`

: The number I picked is lower than your guess (i.e.`pick < num`

).`1`

: The number I picked is higher than your guess (i.e.`pick > num`

).`0`

: The number I picked is equal to your guess (i.e.`pick == num`

).Return the number that I picked.

### 例子

#### 例子 1

Input:`n = 10, pick = 6`

Output:`6`

#### 例子 2

Input:`n = 1, pick = 1`

Output:`1`

#### 例子 3

Input:`n = 2, pick = 1`

Output:`1`

### Constraints

`1 <= n <= 2^31 - 1`

`1 <= pick <= n`

### 解题思路

在给定范围内猜一个数，用简单的二分查找即可。每次猜错时表明中间数不在搜索范围，因此收缩左/右边界时应该收缩到中间值右/左移一位。代码如下：

```
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = ((long)left + right) / 2;
if (guess(mid) == 0) {
return mid;
} else if (guess(mid) == 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
};
```

**时间复杂度**:`O(log n)`

**空间复杂度**:`O(1)`

GitHub 代码同步地址： 374.GuessNumberHigherOrLower.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions