可以直接转为浮点数二分

class Solution {
public:
    int mySqrt(int x) {
        double l = 0, r = x;
        while (r - l > 1e-8)
        {
            double mid = (l + r) / 2;
            if (mid * mid >= x) r = mid;
            else l = mid;
            cout << mid <<' ' << l << endl;
        }
        return r;//注意最后要返回r
    }
};

模板一的看过来
check函数为mid > x / mid 最终找到的为大于根号x的第一个数 即最大值最小，最后讲其减一即为答案

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1) return x;   //j将特殊情况进行特判 1. 防止while 一开始就进不去  2. 进去之后mid可能存在0的风险

        int  l = 0, r = x;
        while(l < r)
        {
            int mid = l + r + 0ll >> 1 ;
            if(mid > x / mid)  r = mid;
            else l = mid + 1 ;
        }

        return l - 1 ;
    }
};

不错，可以的。

class Solution {
public:
    int mySqrt(int x) {
        int l = 0,r = x;
        while(l < r){
            int mid = l + r >> 1;
            if(mid * mid >= x) r = mid;
            else l = mid + 1; 
        }
        return r;
    }
};

这是我开始用模板一做的，开始一直没明白为啥错了，后来看到你的上取整反应过来，我算出来的是上取整的值

long long mid=(l+r+1)/2 把mid定义成long long为啥会不行呢

因为是先对等号右边进行运算，右边是int型运算后已经溢出了

这个check判定函数是根据实际题目需求，抽象出来的。

这里为什么l要从0开始，而不是1？
x不是非负整数么。

写0也是可以的，不影响正确性和时间复杂度。

弱鸡悄悄问一下，这个+1ll是啥意思

1ll是long long类型的1，这样可以把计算结果强制转化成long long，防止结果溢出。

请问一下这里为什么只能用第二个模板，用第一个模板就不行呢

区间更新方式有两种：
1. l = mid + 1; r = mid;
2. l = mid; r = mid - 1;
如果是第一种，用第一个模板；如果是第二种，用第二个模板。

我本来以为是可以使用第一个模板的，使用mid>x/mid 输出的都比你要的结果大1，但是如果输入为 0 的话（未进入循环），输出结果就不比答案大1，而如果是1的话，就不再绿色上，也得不到答案。所以还是直接使用模板二比较好

使用mid > x / mid和mid <= x / mid是等价的，相当于只是交换了if-else的位置。本题如果要使用模板二，需要用mid >= x / mid，此时二分出的是大于等于 $\sqrt x$ 的最小整数，二分之后还要特判一下，如果严格大于 $\sqrt x$，那么需要将答案减一。比较麻烦，所以推荐模板二。

就是这个意思 需要加特判 去掉特殊情况

好滴。

模板一AC代码

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1) return x;   //j将特殊情况进行特判 1. 防止while 一开始就进不去  2. 进去之后mid可能存在0的风险

        int  l = 0, r = x;
        while(l < r)
        {
            int mid = l + r + 0ll >> 1 ;
            if(mid > x / mid)  r = mid;
            else l = mid + 1 ;
        }

        return l - 1 ;
    }
};

可以的。

可以理解为 （0，n） 区间，相当要查找的目标区域位于 右边区间，所以使用模板二

l最后为什么要减1？

这里当x为最大值时， （l + r + 1) 会溢出
应该改成 mid = l + ( r - l + 1) / 2 ;

已改hh

今天看了二分的视频，原来我说的两个都会溢出，QAQ

直接把计算结果强制转化成long long比较稳hh

如果是java怎么防止溢出呢？

转化成long类型