算法：69.x的平方根
题目
链接：leetcode链接
思路分析（二分算法）
当然你可以使用暴力查找，但是二分算法的时间复杂度更好。
我们先用暴力查找找点灵感
x ：1 2 3 4 5 6 7 8
x2：1 4 9 16 25 36 49 64
我们的目的是找到一个x使得x2恰好小于target
观察x2序列，我们可以发现分成两部分，一边 <= target，另一边大于 target,
由此，我们就发现了二段性，于是理所当然使用二分算法。
一些细节问题
1、这里使用的是寻找右边界的二分算法，left < right , mid = left + (right - left + 1) / 2;
2、target的范围是int，但mid * mid可能超出int的范围，需要把mid设置成long long类型
3、right - left + 1，因为这里出现了 + 1,所以可能超出int的范围，所以left就不从0开始，从1开始即可，对0进行特判即可。
代码
int mySqrt(int x) {
if(x == 0)
return 0;
int left = 1,right = x -1;
while(left < right)
{
long long mid = left + (right - left + 1) / 2;
if(mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}
原文地址：https://blog.csdn.net/2303_78940834/article/details/142501298
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！