类似博文：LeetCode35. 搜索插入位置 --（数组） 简单（二分法查找）--总结
题目描述
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
解题思路
使用了二分查找
定义left right mid
//（c++实现）
class Solution {
public:
int mySqrt(int x)
{
if (x <= 0)
return 0;
int left, right, mid;
left = 1;
right = x;
// mid = left + (right - left) / 2; //定义为加(left+right)/2则会出错 原因是整形溢出
while (left <= right)
{
mid = left + (right - left) / 2;
if (mid > x / mid)
right = mid - 1;
else if (mid < x / mid)
left = mid + 1;
else
return mid;
//mid = left + (right - left) / 2;
//mid =(left+right)/2;
}
return right;//注意必须为right
}
};
标准的二分法：
参考：【1】https://www.jianshu.com/p/f1d4a1a8efd2
【2】 https://blog.csdn.net/lu597203933/article/details/44851777
该解法不错：
二分
//（c++实现）
class Solution {
public:
int mySqrt(int x)
{
double begin = 0;
double end = x;
double result = 1;
double mid = 1;
while(abs(result-x) > 0.000001)
{
mid = (begin+end)/2;
result = mid*mid;
if(result > x) // 二分的范围
end = mid;
else
begin = mid;
}
return (int)mid;
}
};
模板的实现
//Java
class Solution {
public int mySqrt(int x)
{
// 注意：针对特殊测试用例，例如 2147395599
// 要把搜索的范围设置成长整型
long left =0;
long right = x / 2 + 1;//缩小范围
//排除上述特殊情况后，依据题目可以确定目标值一定在在左右边界之中
while (left < right)
{
long mid = left + (right - left+1) / 2;//取右中位数为此需要加1
if (mid*mid >x) //依据题目排除中位数（此判断中位数大于目标值，而题目要找的是小于或等于目标值的第一个元素）
{
right = mid -1;
}
else //
{
left = mid;//若 mid 选择左中位数，则只剩下两数时，下次还选择left那么会一直进入死循环
}
}
//循环结束只剩下最后一个值
return (int)right;
}
}
时间复杂度：O (logN)
空间复杂度：O (1)
牛顿迭代法：
设r是f(x) = 0的根，选取x0作为r初始近似值，过点（x0,f(x0））做曲线y = f(x）的切线L，L的方程为y = f(x0)+f'(x0)(x-x0），求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0），称x1为r的一次近似值。过点（x1,f(x1））做曲线y = f(x）的切线，并求该切线与x轴交点的横坐标 x2 = x1-f(x1）/f'(x1），称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中x(n+1）=x(n）－f(x(n))/f'(x(n)），称为r的n+1次近似值，上式称为牛顿迭代公式。
定义问题，
设f(x)=x^2-x* 目标是让f(x)逼近0
由x(n+1）=x(n）－f(x(n))/f'(x(n)）
可知：x(n+1)=x(n)-{x(n)^2-x*}/2x(n)
=x(n)/2+x*/2x(n)
其中的x*为本题的x(n)表示前一次的值
//（c++实现）
class Solution {
public:
int mySqrt(int x)
{
//*牛顿迭代法*/
double pre = 0;
double cur = x;
while(abs(cur - pre) > 0.000001)
{
pre = cur;
cur = (pre/2 + x/(2*pre));
}
return int(cur);
}
};
//Java
public class Solution
{
public int mySqrt(int a)
{
double pre = 0;
double cur = a;
if (cur<0)
{
return(-1);
}
while(Math.abs(cur - pre) > 0.000001)
{
pre=cur;
cur=(pre/2 + a/(2*pre));
}
return (int)cur;
}
}
