374. Guess Number Higher or Lower.md

374. Guess Number Higher or Lower

思路

二分法。
注意计算mid的时候防止溢出，见代码。

C++

// 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, mid;
        while(low <= high){
            mid = low + (high - low) / 2;  // 不用 mid = (low + high) / 2, 因为这样可能溢出
            if(guess(mid) == 0) return mid;
            else if(guess(mid) > 0) low = mid + 1;
            else high = mid - 1;
        }
    }
};