69 Sqrt(x)

69. Sqrt(x)

1. Question

Implementint sqrt(int x).

Compute and return the square root ofx.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4

Output:2

Example 2:

Input: 8

Output: 2

Explanation:
The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will betruncated.

2. Implementation

(1) Binary Search

思路：由于这题要求结果是整数，这就相当于找一个整数num <= sqrt(x), 是找右边界， 可以直接套用二分法的找右边界的模板

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        int start = 1, end = x, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (mid > x / mid) {
                end = mid - 1;
            }
            else {
                start = mid;
            }
        }

        if (end <= x / end) {
            return end;
        }
        else {
            return start;
        }
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(logx), 空间复杂度O(1)