【Day 37】69. x 的平方根.md

思路

二分查找，因为结果res**2 <= x，且res是整数，可以通过二分查找来确定。

代码

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

    }
}

复杂度分析

• 时间复杂度：O(logx)。
• 空间复杂度：O(1)。