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.

思路

注意，这里有几个陷阱，一是你要理解my的含义，它的my是指的出题人，而我们是解题人，所以如果返回-1，说明它的数小，我们猜的数大，这里一定要理解！

这是一个经典的二分题目，很容易套用二分查找的公式写出来：

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int st = 1, ed = n;
        while(st < ed)
        {
            int mid = (st + ed) / 2;
            if(guess(mid) == 0)
                return mid;
            else if(guess(mid) < 0)  // the number is too large
                ed = mid-1;
            else
                st = mid+1;
        }
        return st;
    }
}

看上去没问题，但是实际上有潜在的危险，比如这个例子就A不过去：

为什么，因为int mid = (st + ed) / 2;可能会由于（st+ed）产生溢出！！

所以，为了解决这个问题，推荐把mid的写法写成下面的格式：

int mid = st + (ed - st) / 2;

然后再A就能通过