java - 如何正确实现二分搜索算法来猜测 Java 中的随机 BigInteger？

Question

我正在编写一个程序，该程序应该猜测另一个程序随机生成的 BigInteger。数字类提供关于我的猜测是否高于或低于数字的反馈(如果答案正确，则为“正确”)。虽然我的程序运行良好并正确猜测 BigInteger，但我实现的二分搜索算法的执行效率低于我的预期。我绞尽脑汁也想不通为什么猜测次数(找到该位后)超过了 log(n) 时间。

我一直在计算猜测的数量，并且我的代码的第一部分(找到大整型的正确位)表现得非常好，通常只需要少量猜测。

public static BigInteger guesser(Number n) {
    int guesses=0;

    String feedback = n.guess(BigInteger.ONE); 
    guesses++;

    if (feedback.equals("correct")){
        return BigInteger.ONE;

    } else{
        BigInteger two = new BigInteger("2");
        BigInteger max = two;
        BigInteger min = max;
        BigInteger mid;

        if(n.guess(max).equals("correct")) {
            return max;
        }

        while (!feedback.equals("lower")) {
            min = max;
            max = max.pow(2);
            feedback=n.guess(max); 
                    guesses++;
        }

        mid = min.add(max).divide(two);
        feedback = n.guess(mid); 
            guesses++;

        while (!feedback.equals("correct")){
            if (feedback.equals("higher")){
                min=mid.add(BigInteger.ONE);
            } else if (feedback.equals("lower")){
                max=mid.subtract(BigInteger.ONE);
            } 
            mid= min.add(max).divide(two);
            feedback = n.guess(mid); 
                guesses++;
        }
        return mid;
    }

代码的二分搜索算法部分进行了大量的猜测，我不明白为什么。对于 38119 位 BigInteger，程序大约需要两倍的猜测次数。我是否在做一些根本性错误的事情，或者这里是否有一个我忽略的简单错误？猜测次数不应该大约等于2log(n)吗？

Answer 1

问题是你的指数搜索走得太高了。当数字足够大时，您找到的第一个数字比需要的要高得多。

假设您要猜测的数字是 43263289412904812894021841098214912804215324，通过应用 pow(2) 查找上限，您要猜测的第一个数字是 115792089237316195423570985008687907853269984665640564039457584007913129639936 - 这要高得多，需要多次尝试才能返回到附近。

现在假设您应用了 multiply(new BigInteger("25")) - 您输入的第一个数字是 43368086899420177360298112034797668457031250。是的，需要更多的尝试才能达到这个数字，但最终这是值得的，因为在如此巨大的数字上的最后一个 pow(2) 造成了如此大的杀伤力，以至于很难回来。我在这里使用了一个小数字，但数字越大，情况就越糟糕。

在我看来 - 在寻找上限的同时，你应该在应用 pow 和乘法之间找到平衡。也许如果一个数字足够大，那么停止求幂并开始乘以某个值，并随着界限变高而使该值变高。

我在上面的示例中使用了一个较小的值，但使用 38119 位 BigInteger:

• pow(2) - 上限 17 个猜测 - 所有猜测 65552
• multiply(new BigInteger("25")) - 上限 8209 个猜测 - 所有猜测 46327 个
• multiply(new BigInteger("100")) - 上限 5738 个猜测 - 所有猜测 43854 个
• multiply(new BigInteger("1000")) - 上限 3826 个猜测 - 所有猜测 41946 个
• multiply(new BigInteger("10000")) - 上限 2870 个猜测 - 所有猜测 40994 个
• multiply(new BigInteger("50000")) - 上限 2443 个猜测 - 所有猜测 40562 个
• multiply(new BigInteger("100000")) - 上限 2296 个猜测 - 所有猜测 40416

需要进行更多猜测才能达到上限，但随后我们更接近最终值，因此仍然值得。请注意，它在某个时候不再有值(value)。