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