Q：
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 : My number is lower 1 : My number is higher 0 : Congrats! You got it!
Example: n = 10, I pick 6.Return 6.
A：
Binary search二分法檢索時間復雜度O(log?2??n)六荒。(三分法worst case時間復雜度是O(log?3n))
先比較mid key，大了钓试，往mid后面找，小了往前面找斯棒。
每次没龙，沒找到链韭，重新設定邊界值start和end。
public int guessNumber(int n) {
int start = 1, end = n;
while(start < end) {
int mid = start + (end - start) / 2; //備注
if(guess(mid) == 0) {
return mid;
}
else if(guess(mid) == 1) { //說明target比mid值要大
start = mid + 1; //起點設置為mid后一位
}
else { //說明target比mid值要小
end = mid; //終點設置為mid
}
}
return start;
}
備注：不能寫成 mid = (start+end)/2浙垫，會integer overflow刨仑。
比如測試用例 （2126753390，1702766719）：
overflow一開始不會夹姥，2126753390+1并沒有超過Integer最大值2147483647杉武，但是尋找的這個target=1702766719，那么需要重新設定start值=mid值(106337670)辙售，這是再計算(mid+end)/2轻抱，加法得到319013009超過了Integer的最大值，導致overflow旦部。如果mid+(end-mid)/2則不會祈搜。
