LeetCode 69.x的平方根

主页有其他数据结构内容（持续更新中）

难度：Easy

代码：

法一：二分查找

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = (x >> 1) + 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            //  用mid * mid <= x 可能会溢出，因此用除法表示
            if (mid <= (x / mid)) {
                if ((mid + 1) > (x / (mid + 1))) {
                    return mid;
                }
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return 0;       
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

法二：牛顿迭代法
用切线不断逼近

class Solution {
public:
    int mySqrt(int x) {
        int a = x;
        long long ans = x;
        while(ans * ans > x){
            ans = (ans + a / ans) / 2;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11