【C++】二分查找算法：x的平方根

本文主要是介绍【C++】二分查找算法：x的平方根，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目

2.算法思路

看到题目可能不容易想到二分查找。

这题考察我们对算法的熟练程度。

二分查找的特点：数组具有二段性(不一定有序)。

题目中没有数组，我们可以造一个从0到x的数组，然后利用二分查找找到对应的值即可。

3.代码

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

时间复杂度：O(logn)。

这篇关于【C++】二分查找算法：x的平方根的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---