题目的主要信息：

• 输入一个整数，求其平方根
• 向下取整
• 要求：空间复杂度 $O(1)O(1)$，时间复杂度 $O(lo{g}_{2}x)O(log\_2x)$

方法一：相加和

具体做法：

数学定理：从1开始的连续n个奇数相加的结果一定是n的平方数。

比如：1+3=4，1+3+5=9，1+3+5+7=16等等。

我们可以用x减去从1开始连续的奇数，直到x小于等于为止，等于0说明刚好可以有整数平方根，小于0说明没有整数平方根，这时候我们向下取整需要减去多算的一次。

class Solution {
public:
    int mysqrt(int x) {
        int res = 0;
        for(int i = 1; x >= 0; i += 2){ //记录n个奇数相加
            x -= i;
            res++;
        }
        return res - 1; //向下取整
    }
};

复杂度分析：

• 时间复杂度：$O(x)O(\backslash mysqrt\; x)$，遍历次数最多为$xx$的平方根加1
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：二分法

具体做法：

求平方根，可以看成在1-x之间找一个整数m，该整数满足，有序数组中查找一个数字，我们可以使用二分法。

从数组首尾开始，每次查找区间中点，如果中点过小就查找右半区间，如果中点过大就查找左半区间，直到左右重合或者找到。

class Solution {
public:
    int mysqrt(int x) {
        if(x == 1)
            return 1;
        int l = 1, r = x; //平方根一定在1-x之间
        while(l <= r){
            int m = (l + r) / 2; //从中间二分找
            if(m <= x / m && (m + 1) > x / (m + 1)) //夹在中间
                return m;
            if(m > x / m) //在左半区间
                r = m - 1;
            else //在右半区间
                l = m + 1;
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}x)O(log\_2x)$，二分法最坏情况对x取对数
• 空间复杂度：$O(1)O(1)$，无额外空间