当前位置：首页 > article >正文

【CSDN Daily Practice】【二分】X的平方根

article 2024/11/18 17:43:32

【CSDN Daily Practice】【二分】X的平方根

官方思路：经典二分法，傻白甜地给了个最大值46340


class Solution {
    public int mySqrt(int x) {
        int left = 0, right = 46340;
        while (left < right) {
            int mid = (left + right) / 2;//建议使用left + (right-left)>>>1
            if (mid * mid < x)
                left = mid + 1;
            else if (mid * mid > x)
                if ((mid - 1) * (mid - 1) <= x) // 往小一值探测
                    return mid - 1;
                else
                    right = mid - 1;
            else
                return mid;
        }
        if (left * left > x)
            return left - 1;
        return left;
    }
}

建议使用渐进二分法，不需要定义最大值

public int mySqrt2(int x) {
        int k = 0;
        int step = x/2;
        while (step >= 1) {
            while((k+step)*(k+step) <= x){
                k += step;//逼近
            }
            step /= 2; //砍半
        }
        return k ;
    }