思路和时间复杂度

1. 思路：二分寻找符合要求的元素，在mid小于当时的元素时，记录更新结果，这样可以满足要求，而且由于是计算平方，所以可以右边界为之前的一半
2. 时间复杂度：       

代码

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;}
};