69. Sqrt(x)

题目

思路：从1 - x 查找 res * res = x; 可以采用二分查找的算法。
注意溢出问题。
当left <= right 没有找到值是，就是小数， 类似 Sqrt(8) = 2.8..； 在2 - 3 之间。最后返回的时候返回right，因为right比left小。

public static int sqrt(int x)
    {
    if (x <= 1) {
        return x;
    }

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