找到最快满足gt(大于条件)的数字的算法

Question

我必须检查一个数字是否会导致某种类型的溢出。

例如，如果我们假设溢出数为98，那么一种非常低效的方法是从1开始，一次递增1。这需要98次比较。

我想出了一个更好的方法来做这件事，所以

它的基本作用是在已知的失败条件后将检查更改为2的下一次幂，例如，我们知道0失败，所以我们从1开始检查，然后是2,4,8，。。。，128.128次通过，所以我们检查64+1,64+2,64+4，。。。，64+32，它通过了，但我们知道64+16失败了，所以我们在1+（64+16）==1+80开始下一轮。这是一个视觉效果：

1   1
2   2
3   4
4   8
5   16
6   32
7   64
81  128 ->
9          1, 64 // 1 + 64
10         2, 64
11         4, 64
12         8, 64
13         16, 64
14         32, 64 ->
15                  1, 80
16                  2, 80
17                  4, 80
18                  8, 80
19                  16, 80
20                  32, 80 ->
21                            1, 96
22                            2, 96 // done

有更好的方法吗？

Answer 1

如果你不知道最大值，我认为用你的初始方法来找到MIN=64，max=128的范围是好的。在找到最小值/最大值后进行二进制搜索将是最有效的（例如，查看96，如果它导致溢出，则您知道范围是最小值=64，最大值=96）。你在每一步都将范围减半，你会更快地找到解决方案。

既然98是你的答案，下面是二进制搜索的结果。这需要13个步骤，而不是22:

// your initial approach
1   1
2   2
3   4
4   8
5   16
6   32
7   64
8   128 ->
// range found, so start binary search
9          (64,128) -> 96
10                  (96,128) -> 112
11                          (96,112) -> 104
12                                 (96,104) -> 100
13                                        (96,100) -> 98 // done
// you may need to do step 14 here to validate that 97 does not cause overflow
// -- depends on your exact requirement

Answer 2

如果你知道"溢出函数"是单调递增的，你可以一直加倍，直到你过去，然后应用经典的二进制搜索算法。这将为您提供以下搜索顺序：

1
2
4
8
16
32
64
128 -> over - we have the ends of our range

在[64..128]范围中运行二进制搜索

64..128, mid = 96
96..128, mid = 112
96..112, mid = 104
96..104, mid = 100
96..100, mid = 98
96..98,  mid = 97
97 - no overflow ==> 98 is the answer

Answer 3

以下是我如何在javascript:中实现这项技术

function findGreatest(shouldPassCallback) {
    function findRange(knownGood, test) {
        if (!shouldPassCallback(test)) {
            return [knownGood, test];
        } else {
            return findRange(test, test * 2);
        }
    }
    function binarySearchCompare(min, max) {
        if (min > max) {
            throw 'Huh?';
        }
        if (min === max) { return shouldPassCallback(min) ? min : min - 1; }
        if (max - min === 1) { return shouldPassCallback(max) ? max : min }
        var mid = ~~((min + max) / 2);
        if (shouldPassCallback(mid)) {
            return binarySearchCompare(mid, max);
        } else {
            return binarySearchCompare(min, mid);
        }
    }
    var range = findRange(0, 1);
    return binarySearchCompare(range[0], range[1]);
}