[LeetCode]Sqrt

两种方法，二分查找和牛顿迭代。首先讲一下二分查找，先上代码：

	public class Solution {
	public int sqrt(int x) {
	if (x == 0 || x == 1)
	return x;
	int lo = 1, hi = x, mid = 0;
	while (lo <= hi) {
	mid = lo + (hi - lo) / 2;
	if (x / mid > mid)
	lo = mid + 1;
	else if (x / mid < mid)
	hi = mid - 1;
	else
	return mid;
	}
	return hi;
	}
	}

view raw sqrt v-1.java hosted with ❤ by GitHub

首先明确的是返回的是sqrt的整数部分。我们二分循环的跳出条件是lo > hi，那么当我们跳出的时候我们返回hi为什么一定是正确答案呢？我们来证明这一点：

• 假设跳出之前执行了lo = mid + 1，说明最后找到的整数小于实际sqrt的值，那么结果在(hi, hi + 1)中，hi的位置就是原来lo的位置。返回hi就是整数部分。
• 假设跳出之前执行了hi = mid - 1，说明最后找到的整数大于实际sqrt的值，那么结果在(hi, hi + 1)中，hi为更新后的hi。返回hi就是整数部分。

除此之外，根据我们之前总结的二分的边界条件，我们可以对二分做适当的修改，仍然使结果正确，代码如下：

	public class Solution {
	public int sqrt(int x) {
	int lo = 0;
	int hi = x;
	if (x == 1)
	return 1;
	while (hi - lo > 1) {
	int mid = (lo + hi) / 2;
	if (x / mid > mid)
	lo = mid;
	else if (x / mid < mid)
	hi = mid;
	else
	return mid;
	}
	return lo;
	}
	}

view raw sqrt v-2.java hosted with ❤ by GitHub

这里我们跳出二分的边界条件是lo + 1 >= hi，注意这里我们每次把[lo, hi]分成[lo, mid] + [mid, hi](这里注意虽然我们这样分，但其实结果是在[lo, mid) 或者 (mid, hi]里的，因为如果等于mid程序就不会进行下去，如果能进行下去，结果一定不是mid)。因为我们特殊考虑了输入是1的情况，所以我们跳出的时候一定是lo + 1 == hi的，表明结果在一定在(lo, hi)范围内，注意这里由于只有当左右边界是起始lo或者hi的话才会是inclusive的，但是由于我们特殊考虑了1的情况，1和n都不会是答案，所以结果在(lo, hi)而不是[lo, hi)或者(lo, hi]，那么返回整数部分我们返回lo就行。


下面说说牛顿迭代法(参考Annie's Blog)，算sqrt就跟找f(x) = x^2 - n，和x轴的交点是一样的。如下图所示(图片来自Annie's Blog)：

先给定一个起始x，如果不是解，就做切线找和x轴交点，直到找到为止。切线的方程式2x0 * (x - x0) = y - (x0^2 - n)，令y等于0，结果就是x  = (n / x0 + x0) / 2，我们只需一直套用迭代方程直到结果变动可以忽略不计为止。注意这里用do-while比用while效果更好，代码如下：

	public class Solution {
	public int sqrt(int x) {
	double res = 1;
	double copy;
	do {
	copy = res;
	res = (x / res + res) / 2;
	} while (Math.abs(res - copy) > 1e-7);
	return (int)res;
	}
	}

view raw sqrt v-3.java hosted with ❤ by GitHub

值得一提的是牛顿迭代比二分要快，据说还有一个更变态的sqrt的方法，有兴趣的请google黑魔法数。