最快找到满足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，如果它导致溢出，那么您知道范围是 MIN=64，MAX=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