69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

S: binary search O(logn)

corner case和溢出处理

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

367. Valid Perfect Square

Given a positive integernum, write a function which returns True ifnumis a perfect square else False.

Note:Do notuse any built-in library function such assqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

S： binary search （Logn)

    bool isPerfectSquare(int num) {
        if (num < 4) return num == 1;
        int left = 1, right = num / 2;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (mid * mid == num) return mid;
            if (mid < num / mid) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left * left == num || right * right == num;
    }