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)。