建行网站/网页搜索优化

关键字：二分查找，数值分析

Problem

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4 输出: 2

示例 2:

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

Solution 1: binary search

这道题出现的标签有两个，二分查找和数学。首先使用一下二分查找方法。二分查找的关键就是找到符合要求的区间。对此我想到了逐次加倍的方法来缩小区间。具体来说，就是令初始结果为 1，如果初始结果的平方小于等于 x，就继续加倍。这里实际上是来源于 Hash 表和我阅读的数据结构书籍中自己实现 std::vector class 中动态调整数组容量的加倍操作的灵感。

long y = x;
long begin = 1;
while (begin*begin <= y)begin *= 2;

那么最后得到的区间

中一定包含了平方根的结果，之后就是运用二分法来快速查找。

long end = begin;
begin = begin/2;
while (begin < end){long mid = begin+(end-begin)/2;if (mid*mid == y){return mid;}else if (mid*mid < y){begin = mid+1;}else{end = mid;}
}
return (begin*begin == x) ? begin : begin-1;

由于这里得到的 begin 实际上是平方不小于 begin 的最小值，因此最后还要做一次判断是否是完全平方数。时间复杂度上，第一部分循环体的执行次数

满足：

，因此

的数量级是

。之后第二次的话是在一个长度为

的范围内进行二分查找，因此时间复杂度是

，因此总的数量级是

。

合并可以得到这个代码：

class Solution {
public:int mySqrt(int x){if (x){long y = x;long begin = 1;while (begin*begin <= y){begin *= 2;}long end = begin;begin = begin/2;while (begin < end){long mid = begin+(end-begin)/2;if (mid*mid == y){return mid;}else if (mid*mid < y){begin = mid+1;}else{end = mid;}}return (begin*begin == x) ? begin : begin-1;}else{return 0;}}
};

但是这个地方还有两个值得注意的细节。首先是类型溢出问题，例如上述的 y 和 begin，end 中最好都用 long 类型，否则会溢出，这个我已经出错过了，解决方法就是加上 long。

其次是结果到底是什么的问题。根据这段中间的二分查找的算法可以知道实际上求的是使得

的最小的 begin，而如果 x 不是完全平方数，那么应该返回 begin-1。

Solution 2: numerical analysis

这实际上可以当成在只有加减乘除四则运算的情况下求解方程

，其中

的问题。这让我不由得想到了一道高考题。

(2014 安徽卷理科，21）
设实数

，整数

，

(1) 证明：当

，且

时，

(2) 数列

满足

，

，求证：

简单说明一下这道高考题的解答。第一问是 trivial 的，这是熟知的 Bernoulli 不等式（百度百科/维基百科）的特殊情况，可以求导也可以直接二项式定理。第二问首先证明，当首项大于

时，后面每项都大于

，这可以求导结合数学归纳法解决。其次只需要作差来证明差的单调性，仍然是求导。更详细的解答可以参考我阅读过的这个知乎文章：

回到原题。本题就是

的特殊情况，只需要照这个算法去做就行了。问题的关键在于找到一个合适的

出来。容易想到，

，那么就直接令

就行了，然后恭喜我迎来了又一个 runtime error：

那么不妨换个思路。注意到熟知的基本不等式：

，如果令

，

，容易注意到这个时候

肯定是不超过范围的，下面我们来证明：

注意到：

，因此

时是成立的，显然

也成立，那么就证完了。

另外，由于我们要的条件只需要正整数，那么终止条件可以写的更随意一些，就是迭代前后的整数部分不变。因此我们可以写出以下代码：

class Solution {
public:int mySqrt(int x){double y = x/2+1;while ( int(y) - int(0.5*y + x/(2*y)) > 0){y = 0.5*y+x/(2*y);}return y;}
};

根据数值分析理论，这个迭代过程是二阶收敛的，意味着比线性收敛要快很多，具体证明参考上述高考题分析链接。

EOF。