algorithm - 如何设计有效的最小上界搜索算法

Question

假设您有一组具有已知下限和未知上限的数字，即 0、1、2、3 ... 78，其中 78 是未知数。目前假设数字之间没有间隙。有一个耗时的函数 test() 可以测试一个数字是否在集合中。

什么是找到集合中最高数字的有效方法(需要少量的 test() 调用)？

如果您知道上限是 75 +/- 25 怎么办？

如果集合中的数字之间存在随机间隙，即 0、1、3、4、7、... 78，会怎样？

Answer 1

对于“无间隙情况”:

• 我假设这是一个固定大小的数字，例如一个 32 位整数
• 我们希望找到 x 使得 test(x) == true，test(x+1) == false，对吗？

您基本上是在最低已知“不在集合中”(例如最大的 32 位 int)和最高已知“在集合中”(开始具有已知的下限)通过每次测试范围内的中间值并相应地调整边界。这将给出一个 O(log N) 解决方案(根据 调用 test() 的次数)，其中 X 是潜在 集的大小，而不是实际 集的大小。对于小集合，这将比仅尝试 1、2、3... 慢，但对于大集合要快得多。

如果存在差距，所有这些都会下降，在这一点上，我认为除了“从绝对最大可能的数字开始并一直工作直到 test(x) == true< 之外没有任何可行的解决方案 在这一点上是最高的数字”。据我所知，任何其他策略都将失败或成本更高。