Sqrt(x)

https://leetcode.com/problems/sqrtx/description/

Implementint sqrt(int x).

Compute and return the square root ofx.

x is guaranteed to be a non-negative integer.

Thoughts

这道题可以用二分法做， 即每次取[1, x/2]中值 (x/2因为只要sqrt大于2就一定会比x/2小), 判断mid ^ 2是大于还是小于等于x。 注意最开始的几个值可能溢出, 因此初始end 取46340即可。

还有可以用牛顿迭代法做. 每次取切线与0的交点r, 看r ^ 2 是否>x, 是则继续, 否则返回.

https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95

https://www.zhihu.com/question/20690553

Code

/*
 * @lc app=leetcode id=69 lang=cpp
 *
 * [69] Sqrt(x)
 */
class Solution {
public:
    int mySqrt(int x) {
        int start = 1, end = min(x / 2, 46340);
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (mid * mid < x) start = mid + 1;
            else end = mid;
        }
        return start * start > x ? start - 1 : start;
    }
};



class Solution {
    public int mySqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
}

Analysis

未知.