求平方根（二分）

题意

求一个整数的平方根,向下取整

思路分析

题意转换

要求x的平方根n向下取整

换句话说就是找到

整数上单调性质

对于整数从$00$到$n^{2}n^2$, 单调递增, 与x的大小关系,也是从小于到大于

二分法

有了上述的转换题意和单调性质后,考虑二分.

定义左右值

l左值,它的平方小于等于x

r右值,它的平方大于x

每次取均值(l+r)/2,检验与x大小关系后更新l或r

直到l+1 == r,输出l即可

题目样例

以题目样例为例x=2

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        long long l = 0; // 保证小于等于
        long long r = x+1; // 保证大于
        while(l+1<r){
            long long m = (l+r)/2;
            if(m*m > x){ // 检验
                r = m;
            }else{
                l = m;
            }
        }
        return l;
    }
};

复杂度分析

空间复杂度: 只用了常数个额外变量,所以空间复杂度为$O(1)O(1)$

时间复杂度: 每次让左右值间距减半,所以时间复杂度为$O(log(n))O(log(n))$