[LeetCode] Sqrt(x) 解题报告

Implement int sqrt(int x).

Compute and return the square root of x.

» Solve this problem

[解题思路]
二分法。但是这题有意思的是，二分过程中终止条件的确认。因为整数的乘法有可能导致溢出，而这种溢出的检测跟整数加法直接判断是否小于0是不同的，因为整数的乘法有可能引起多次溢出，当奇数次溢出时是负数，但是偶数次溢出时就又变回正数了，比如
2147395599
如果用是否小于0来终止二分的话，它的平方根会返回617921965，而不是46339。

所以，二分的终点确定比较重要，在运算中想通过是否小于0来判断溢出，是不可靠的，最好的办法就是在二分之前，要求end小于sqrt(INT_MAX)。sqrt(INT_MAX)是个常量，所以不算cheat。

1:    int sqrt(int x) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int start =0, end;  
5:      end= x/2<std::sqrt(INT_MAX)? x/2+1:std::sqrt(INT_MAX);  
6:      while(start<= end)  
7:      {  
8:        int mid = (start+end)/2;  
9:        int sqr = mid*mid;  
10:        if(sqr ==x)  
11:        {  
12:          return mid;  
13:        }  
14:        if(sqr<x)  
15:        {  
16:          start = mid+1;  
17:        }  
18:        else  
19:        {  
20:          end = mid-1;  
21:        }  
22:      }  
23:      return (start+end)/2;  
24:    }  

上网搜了一下，更快的方法是牛顿迭代，不过这个太偏数学了。详情见http://www.2cto.com/kf/201206/137256.html
牛顿迭代法

1:       const float EPS = 0.000000001;  
2:       int sqrt(int x) {  
3:            // Start typing your C/C++ solution below  
4:            // DO NOT write int main() function  
5:            if(x==0) return x;  
6:            float dividend = x;  
7:            float val = x;//最终  
8:            float last;//保存上一个计算的值  
9:            do  
10:            {  
11:                 last = val;  
12:                 val =(val + dividend/val) / 2;  
13:            }while(abs(val-last) > EPS);  
14:            int result = val;  
15:            if(result * result > x)  
16:                 result--;  
17:            return result;  
18:       }  

[Note]
1. Line 15 & 16
虽然设置了迭代精度是EPS,但是始终会有迭代溢出的问题。如果漏了这两句的话，在测试2147395599的时候，会返回46340，而不是46339。