题目

sqrt(x)

算法

* 直接模拟

* 牛顿迭代

代码

* 直接模拟

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

* 牛顿迭代

// Newton's method
class Solution {
public:
    int sqrt(int x) {
        if (x == 0) return 0;
        double res = 1, pre = 0;
        while (res != pre) {
            pre = res;
            res = (res + x / res) / 2;
        }
        return int(res);
    }
};