力扣-数组-69 x的平方根
思路和时间复杂度
- 思路：二分寻找符合要求的元素，在mid小于当时的元素时，记录更新结果，这样可以满足要求，而且由于是计算平方，所以可以右边界为之前的一半
- 时间复杂度：
代码
class Solution {
public:
int mySqrt(int x) {
if(x == 0) return 0;
if(x == 1) return 1;
// 左闭右闭区间
long long left = 0, right = x/2;
long long cur = 0;
while(left <= right){
long long mid = (left + right)/2;
if(mid * mid < x){
cur = mid;
}
if(mid * mid == x){
cur=mid;
break;
}else if(mid*mid > x){
right = mid-1;
}else{
left = mid+1;
}
}
return cur;
}
};