## [Leetcode]374. Guess Number Higher or Lower(C++)

### 题目描述

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.
* @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

Built with Hugo
Theme Stack designed by Jimmy