[LeetCode]Sqrt

两种方法，二分查找和牛顿迭代。首先讲一下二分查找，先上代码：
首先明确的是返回的是sqrt的整数部分。我们二分循环的跳出条件是lo > hi，那么当我们跳出的时候我们返回hi为什么一定是正确答案呢？我们来证明这一点：

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

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

这里我们跳出二分的边界条件是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效果更好，代码如下：
值得一提的是牛顿迭代比二分要快，据说还有一个更变态的sqrt的方法，有兴趣的请google黑魔法数。