题解 | #求平方根#

//标准二分法
int Sqrt(int x ) {
        //特殊处理
    if(x<2) return x;
        //长整型防止溢出；平方根一定小于或等于中值，使用X/2会快一点。
    long int  left = 0;
    long int right = x/2;
        //左闭右闭
    while(left<=right){
                //先减后加防止溢出（好习惯），移位加快运算。
        long int middle = left + ((right-left)>>1);
                //修改区间
        if(middle*middle > x){
            right = middle -1;
        }
        else if(middle*middle < x){
            left = middle + 1;
        }
        else return middle;
    }
        //如果没找到，例如2的平方根约为1.4，此时right指向1，left指向2=(middle+1)，返回right即可。
    return right;
}