Sqrt(x) leetcode

Implement int sqrt(int x).
注意这道题是返回int 的平方根 所以:

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

用二分法来判定 逐步找到平方根, 但是要注意的是只要符合 mid^2 <= x < (mid + 1)^2 那么mid就是x的平方根.

另外要注意的是mid^2可能溢出 所以用x/mid >= mid的形式来表示

时间复杂度是O(log(x)) 空间是O(1)

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