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则不会。