69. x 的平方根

实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1:

  1. 输入: 4
  2. 输出: 2

示例 2:

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

解题思路1
拿到本题时，我首先想到的是从1开始枚举，每次通过计算 i*i <= x && (i+1)*(i+1) > x 判断是否是x的平方根，但是对于一个很大的数，每次枚举都有两次乘法操作和两次判断，总体来说太耗时了。

代码实现1

  1. int mySqrt(int x){
  2.     int i;
  3.     long long next;
  4.     for(i=0;i<=x;i++){
  5.         next = (long long )(i+1)*(i+1);
  6.         if( i*i <= x && next > x )
  7.             break;
  8.     }
  9.     return i;
  10. }

解题思路2
自己没想到更好的办法，看了 Leetcode官方题解
题目不让使用平方根的函数，但是可以利用其他数学公式转化为平方根得到结果
69. x 的平方根 - 图1

这里还有个问题需要注意，因为指数函数和对数函数的参数和返回值均为浮点数，而计算机对浮点数的存储是有限的，无法很精确，就会产生误差。因此在得到结果的整数部分 ans 后，我们应当找出ans 与 ans+1 中哪一个是真正的答案。

代码实现2

  1. /*
  2.    sqrt(x) = e^( (1/2)*lnx )
  3. */
  4. int mySqrt(int x){
  5.     if(x == 0)
  6.         return 0;
  7.     int  sqrt1  = exp( 0.5 * log(x) );
  8.     int sqrt2 = sqrt1 + 1;
  9.     if( sqrt1*sqrt1 <= x && (long long) sqrt2*sqrt2 > x )
  10.         return sqrt1;
  11.     else 
  12.         return sqrt2;
  13. }

解题思路3
用二分查找

代码实现3

  1. /*
  2. 用二分查找 ,初始时范围为 [0,x]
  3. 注意结束条件
  4. if（left > right）
  5.     return right 
  6. 实际上是最后几步left和right已经很接近了。
  7. 前前一步，left1 + 1 = right1 ,mid1 = left1,而此时mid1*mid1 <= x,进入下一次调用left2 = left1 + 1 = right1
  8. 前一步，由上次之后，left2 = right1 ,mid2 = left2 = right1 , mid2*mid2 > x ,进入下一次调用 right3 = mid2 -1 
  9. 这步，发现 left2 > right3  ,返回结果实right3,而 right3 = mid2 - 1 =   left2 - 1 =  left1 = mid1
  11. 举个例子，求 8的平方根。
  12. [0,8 ] 8/2 = 4 , 4*4 = 16 > 8    -> 
  13. [0,3], 3/2 = 1,1*1 = 1<8         ->
  14. [2,3],(2+3)/2 = 2, 2*2 = 4 < 8   ->
  15. [3,3],(3+3)/2 = 3, 3*3 = 9 >8    ->
  16. [3,2], 3>2 return 2;
  17. */
  18. //递归版的二分查找
  19. int findSqrt(int left,int right,int x){
  20.      int mid = (left+right)/2;
  21.      if(left > right)
  22.         return right;
  23.      if((long long)mid*mid <= x){
  24.         return findSqrt(mid+1,right,x);
  25.      }
  26.      else
  27.        return findSqrt(left,mid-1,x);
  28. }
  29. int mySqrt(int x){
  30.     return findSqrt(0,x,x);
  31. }