X的平方根。采用二分查找或者牛顿迭代方法。

X的平方根

在不使用sqrt(x)函数的情况下，得到x的平方根的整数部分

示例：

1输入：141
2输出：11

思路

这类题目通常用暴力求解是比较快速的，但是这里涉及到(0, x-1)的区间，可以考虑使用二分查找、牛顿迭代方式，会比暴力求解更加快速

解题

二分法

解法一：二分查找 x的平方根肯定在(0, x)之间，使用二分查找定位该数字，该数字的平方一定是最接近x的，平方值如果大于x、则往左边找，如果小于等于x则往右边找 找到0和x的最中间的数m,如果m * m > x,则m取x / 2到x的中间数字，直到m * m < X,m则为平方根的整数部分如果m * m <= x,则取0到x / 2的中间值，知道两边的界限重合，找到最大的整数，

则为x平方根的整数部分时间复杂度：O(IogN)

 1public static int binarySearch(int num)
 2{
 3    int index = -1;
 4    int left = 0;
 5    int right = num;
 6    while(left <= right)
 7    {
 8        int mid = (left + right) / 2;
 9        if(mid * mid <= num)
10        {
11            index = mid;
12            left = mid + 1;
13        }else
14        {
15            right = mid - 1;
16        }
17    }
18    return index;
19}

牛顿迭代

  1. 通过两个分解的因子，相加起来取平均值，将这个平均值方和目标数比较。
  2. 如果这个平均值没有满足要求，那么把平均值带入原式中，求的目标数与上一步的平均值相除的结果和上一步平均值结果之和的平均值。生成一个新的平均值，然后再次求解平均值方和目标数的对比。
  3. 以此类推，直到得到最终结果
 1public static int newTon(int num)
 2{
 3    if(0 == num)
 4    {
 5        return 0;
 6    }
 7    return (int)sqrt(num, num);
 8}
 9
10public static double sqrt(double i, int num)
11{
12    double res = (i + num / i) / 2;
13    if(res == i)
14    {
15        return i;
16    }else
17    {
18        return sqrt(res, num);
19    }
20}