r题目描述

给定一个非负整数a，求它的开方，向下取整。

思路

  1. 二分法，在[0,a]范围内二分查找
  2. 牛顿迭代法

代码

1. 查找方法

  1. 避免整数溢出
    • (i+j) / 2
    • mid * mid < x
  1.     int mySqrt(int x) {
  2.         if (x == 0) return 0;
  3.         int i = 1;
  4.         int j = x;
  5.         int sqrt = 0;
  6.         while(i <= j)
  7.         {
  8.             int mid = i + (j - i) / 2;
  9.             sqrt = x / mid;
  10.             if (mid  < sqrt)
  11.             {
  12.                 i = mid + 1;
  13.             }
  14.             else if (mid > sqrt)
  15.             {
  16.                 j = mid - 1;
  17.             }
  18.             else
  19.             {
  20.                 return mid;
  21.             }
  22.         }
  24.         return j;
  25.     }
  1. 牛顿迭代法

69. sqrt的实现 - 图1

int mySqrt(int x)
{
  long result = x;
  while (result * result > x)
  {
    result = (x + result / x) / 2;
  }
  return result;
}