leetcode|Leetcode二分查找4:69. x 的平方根 leetcode|c++

链接：https://leetcode-cn.com/problems/sqrtx/
文章图片
https://leetcode-cn.com/problems/sqrtx/
【leetcode|Leetcode二分查找4:69. x 的平方根】该题目让我们不用库函数sqrt(x)，来求x的平方根。
方法一：数学计算
公式变形：sqrt(x)==
文章图片
==
文章图片
,则用lnx函数和exp函数即可求解。
时间复杂度：O(1);
空间复杂度：O(1);
由于计算机无法存储浮点数的精确值，而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x = 2147395600，这样在对结果取整数部分时，得出4633946339 这个错误的结果。所以得多加一步，判断ans和ans+1哪个是真正的答案。

class Solution { public: int mySqrt(int x) { if(x==0){ return 0; } int ans=exp(0.5*log(x)); return (long long)((ans+1)*(ans+1)<=x?ans+1:ans); } };

方法二：二分查找
时间复杂度：O(

文章图片
)，x为二分查找的次数。
空间复杂度：O(1)。

class Solution { public: int mySqrt(int x) { int l=0,r=x,ans=-1; while(l<=r){ int mid=(r-l)/2+l; if((long long)mid*mid<=x){ ans=mid; l=mid+1; } else{ r=mid-1; } } return ans; } };