69. Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Solution：二分查找

思路： 从1 到 x/2中开始二分查找try mid^2 和 x的大小，注意结束条件。
实现Perfer solution2写法
Note: 如果x是小数类型则不能使用x/2，应该用[0, 1]之间，在限制精度内可以用二分查找
Time Complexity: O(logX) Space Complexity: O(1)

Solution Code：

class Solution1 {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        
        int left = 1, right = x / 2;
        int ans = 0;
        while (left <= right) {
            int mid = (right + left) / 2;
            if(mid == x / mid) return mid;
            else if(mid < x / mid) {
                ans = mid;   
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

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