x的平方根（69）

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例

输入: 4 输出: 2

输入: 8 输出: 2

说明: 8 的平方根是 2.82842...,由于返回类型是整数，小数部分将被舍去。

算法

二分查找

我们在[0, x]这个范围内二分查找，找到满足k*k<=x的最大的k的值

export const mySqrt = (x) => {
	let start = 0,
		end = x;
	let res = 0;
	while (start <= end) {
		const mid = ~~((start + end) / 2);
		if (mid * mid <= x) (start = mid + 1) && (res = mid);
		else end = mid - 1;
	}
	return res;
};

牛顿迭代法（牛顿-拉夫逊方法）

求解数字N的平方根，我们可以看作求函数f(x) = x^2-N的非负根

取点(x0, f(x0))（x0大于要求的平方根）,此时过点(x0, f(x0))的切线是f(x0) = 2x0*x-x0^2-N

这条切线与y轴的交点是((x0^2+N)/(2x0), 0)，我们过这点做垂线相交于f(x)，得到新交点，然后过交点做切线，切线交于y轴...如此往复，与y轴的交点会无限趋近于f(x)的非负根

我们每次将与y轴交点向下取整，当其平方恰好不大于我们要求的平方根的N时，即可得到结果

牛顿迭代法 - 百度百科 (opens new window)

export const mySqrt = (x) => {
	let xn = x;
	while (xn * xn > x) {
		xn = ~~((xn * xn + x) / (2 * xn));
	}
	return xn;
};