LeetCode 每日一题 69. x 的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• x 仅仅是 int 范围，开根号在 1e4 ，暴力枚举
• 二分查找
• 牛顿迭代，eps 随手写的

class Solution {
 public:
  int mySqrt(int x) {
    int a = 0;
    while((a + 1) <= x / (a + 1))
      a++;
    return a;
  }
};

/***********************************/

class Solution {
 public:
  int mySqrt(int x) {
    int first = 0;
    int len = INT_MAX;
    int half, middle;

    if(!x)
      return 0;
    while(len > 0) {
      half = len >> 1;
      middle = first + half;
      if(middle > x / middle) {
        len = half;
      } else {
        first = middle + 1;
        len = len - half - 1;
      }
    }
    return first - 1;
  }
};

/*************************/

class Solution {
 public:
  int mySqrt(int a) {
    const double eps = 1e-8;
    double x, x0, f, f1;
    x = 1;
    do {
      x0 = x;
      f = x0 * x0 - a;
      f1 = 2 * x0;
      x = x0 - f / f1;
    } while(fabs(x - x0) > eps);
    return (int)floor(x);
  }
};