使用二进制搜索实现 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：它应该 return 1 但我 return 2。这没有意义，因为我显然采取了中点优先。向左或向右的逻辑不正确吗？

Answer 1

由于您正在对双精度值执行二进制搜索，因此您应该设置一个公差，并在高低差值低于该公差时停止循环（标准公差通常为 1e-6）。您还应该设置 low = mid 或 high = mid 而不是加或减 1，因为您不是对 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;
}

如果您从未预料到需要更高的精度，则可以使用 ints 进行二进制搜索。请参阅下面的代码 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;
}

Answer 2

因为输入是int，结果是int，所以根本不涉及浮点运算。

public static int mySqrt(int i) {
    if (i < 2)
        return i;
    int lower = 0, upper = i;
    do {
        int guess = lower + (upper - lower) / 2;
        if(guess <= i / guess) {
            lower = guess;
        } else {
            upper = guess;
        }
    } while ((upper - lower) > 1);
    return lower;
}

Answer 3

你不应该为此使用任何 double 数学。您必须进行更多次迭代才能获得准确的 double 值，然后就将其丢弃。您应该使用这样的整数解决方案：

int mySqrt(int x) {
    if (x<2) {
        return x;
    }
    int minval=1, maxval=x/2;

    while(minval < maxval) {
        // rounding up here means we never choose minval
        int test = minval + (maxval - minval + 1)/2;
        // testing this way avoids a multiply that could overflow
        if (x/test < test) {
            //too high
            maxval = test-1;
        } else {
            //not too high
            minval = test;
        }
    }
    return minval;
}

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

Implement floored square root using binary search

java

algorithm

binary-search