java - 使用二进制搜索实现 floored 平方根

Question

好吧，我已经研究了一段时间了，我知道我的逻辑是正确的，但是，我似乎无法生成正数的正确底平方根。

    public int mySqrt(int x) {
        if(x < 2) return x;
    
        double lowerBound = 0.0, upperBound = x, midPoint = 0.0;
        while(lowerBound <= upperBound) {

            midPoint = lowerBound + (upperBound - lowerBound) / 2;
            double square = Math.pow(midPoint, 2);

            if(Double.compare(square, x) < 0) lowerBound = midPoint + 1;
            else if(Double.compare(square, x) > 0) upperBound = midPoint - 1;
            else return (int) midPoint;
        }

        return (int) midPoint;
    }

例如，我失败的测试用例是 x = 2:它应该返回 1 但我返回 2。这没有意义，因为我显然先取了一个中点。向左或向右的逻辑不正确吗？

Answer 1

由于您正在对 double 值执行二进制搜索，因此您应该设置一个公差，并在高低差值低于该公差时停止循环(标准公差通常为 1e-6).您还应该设置 low = mid 或 high = mid 而不是加一或减一，因为您不是对 int 值进行二进制搜索。请参阅下面的代码 here .

private static final double TOLERANCE = 1e-10;
public int mySqrt(int x) {
    if (x < 2)
        return x;
    double lowerBound = 0.0, upperBound = x, midPoint = 0.0;
    while (upperBound - lowerBound >= TOLERANCE) {
        midPoint = lowerBound + (upperBound - lowerBound) / 2;
        double square = Math.pow(midPoint, 2);
        if (Double.compare(square, x) < 0)
            lowerBound = midPoint;
        else if (Double.compare(square, x) > 0)
            upperBound = midPoint;
        else
            return (int) midPoint;
    }
    return (int) midPoint;
}

如果您从未预料到需要更高的精度，您可以使用 int 进行二进制搜索。请参阅下面的代码 here .

public int mySqrt(int x) {
    if (x < 2)
        return x;
    int low = 0, high = x;
    while (low < high - 1) {
        final int mid = low + high >>> 1;
        if (mid <= x / mid) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}