Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

求给定数字x的平方根。具体解法类似于一个变形的二分搜索，判断数字1..x的中间数的平方与x的大小来决定在左半边还是右半边继续搜索。

需要小心的是中间变量要用long来保存以防乘法结果溢出。

public int mySqrt(int x) {
    long left = 1;
    long right = x;
    while (left + 1 < right) {
        long mid = left + (right - left)/2;
        if (mid * mid < x) {
            left = mid;
        } else if (mid * mid > x) {
            right = mid; 
        } else {
            return (int) mid;
        }
    }
    if (right * right <= x) {
        return (int) right;
    }
    return (int) left;
    }