算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。是以，為了提高大家的算法能力，這個公衆号後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做 猜數字大小，我們先來看題面：
https://leetcode-cn.com/problems/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 到 n 随機選擇一個數字。 請你猜選出的是哪個數字。
如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了。
你可以通過調用一個預先定義好的接口 int guess(int num) 來擷取猜測結果，傳回值一共有 3 種可能的情況（-1，1 或 0）：
-1：我選出的數字比你猜的數字小 pick < num
1：我選出的數字比你猜的數字大 pick > num
0：我選出的數字和你猜的數字一樣。恭喜！你猜對了！pick == num
傳回我選出的數字。
示例
示例 1：
輸入：n = 10, pick = 6
輸出：6
示例 2：
輸入：n = 1, pick = 1
輸出：1
示例 3：
輸入：n = 2, pick = 1
輸出：1
示例 4：
輸入：n = 2, pick = 2
輸出：2 複制
解題
主要思路：
在調用guess()方法時，傳回結果這裡題目描述的很不清楚，傳回-1，是代表你猜的數字大了。同理，傳回1，是代表你猜的數字小了。了解了這個，就可以很容易的想到使用二分查找了。
要注意在求中間值的時候，注意使用 left + (right - left)/2 來防止溢出
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1;
int right = n;
while (left <= right){
int mid = left +(right - left)/2;
if(guess(mid) == 1) left = mid+1;
else if(guess(mid) == -1) right = mid - 1;
else return mid;
}
return -1;
}
} 複制
好了，今天的文章就到這裡，如果覺得有所收獲，請順手點個在看或者轉發吧，你們的支援是我最大的動力 。