【LeetCode】69. Sqrt(x) 二分查找实现开平方函数

本文主要是介绍【LeetCode】69. Sqrt(x) 二分查找实现开平方函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

翻译：即给定整数x，实现开平方函数。

思路：

           1.任何大于1的整数的开平方一定是大于1、小于x/2+1的，因此可以在[1,x/2+1]区间内使用二分查找来查找这个数。

           2.这个题目还有一个关键问题是，若给定x非常大，计算平方时会溢出，因此数据类型应该设置为long long。

题外话：在做这道题的时候，我可以根据x的位数来确定一个更小的搜索空间，但事实证明，在二分查找下，这样并不能节省太多时间。

代码：

int mySqrt(int x) {if(x<=0)return 0;if(x==1)return 1;long long low=1;long long high=x/2+1;long long mid=0;while(low<=high){long long mid=(low+high)/2;if(mid*mid>x)high=mid-1;else if(mid*mid<x)low=mid+1;elsereturn mid;}return (low+high)/2;
}

这篇关于【LeetCode】69. Sqrt(x) 二分查找实现开平方函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---