在“无限”序列上进行二分搜索，我该从哪里开始？

Question

我遇到了一个有趣的问题。我有一个函数，它需要很长时间才能根据某个索引计算出一个值。我们称这个函数为 takes_a_long_time(index)。这个函数返回的值一定会有一个全局最小值，但并不能保证与这个最小值相关的索引会接近零。

因为 takes_a_long_time 接受任意大的正整数作为索引，所以在开始二分查找时有一些独特的限制。我需要找到一个有限的区间来搜索这个最小值。我的第一个想法是从零开始，检查越来越大的区间。比如说：

def find_interval_with_minimum():
    start = 0
    end = 1
    interval_size = 1
    minimum_in_interval = check_minimum_in(start, end)
    while not minimum_in_interval:
        interval_size = interval_size * 2
        start = end
        end = start + interval_size
        minimum_in_interval = check_minimum_in(start, end)
    return start, end

这看起来是可行的，但还有一个额外的细节让事情变得复杂。随着索引接近零，takes_a_long_time 计算一个值所需的时间会成指数级增加。由于 check_minimum_in 需要多次调用 takes_a_long_time，我希望避免从零开始。

所以我的问题是，考虑到最小值可能在 [0, +无穷) 的任何地方，有没有合理的方法可以“反向”运行这个过程？或者，有没有什么好的经验法则可以用来避免不必要地检查低索引？

我希望能有一种与语言无关的解决方案。不过，我是在用 Python 编写这个，所以如果有特定于 Python 的方法，我也很乐意接受。

Answer 1

听起来我们需要选择一个比较大的数字，这个数字要足够大，以至于 takes_a_long_time 的运行时间不会太长。然后启动两个线程：一个线程向正无穷大查找，试图找到包含最小值的范围；另一个线程则向零的方向查找同样的范围。因为时间复杂度是指数增长的，从搜索的角度看，零就像是无穷大一样。哪个线程先找到结果，就取消另一个线程。

不过，如果你不想利用多个CPU核心，就不要启动两个线程（如果你想用，最好不要只启动两个线程，而是根据核心数量启动一个线程）。可以在两个方向上交替进行工作。

有了这个基本策略后，你需要调整接近零的速度。接近得越快，如果最小值真的在那一侧，找到它所需的步骤就越少，但剩下的范围就会更大，因为你通常会“超越”零。如果性能曲线是反指数型的，那么你就应该尽量少超越，所以应该慢慢接近零。甚至可能你的任务在计算上是不可行的，“指数”通常意味着“不可能”。

显然，我无法告诉你最初的“大的数字”应该是多少。是一百可以接受吗？还是一百万？格雷厄姆数呢？如果你连什么样的性能是可以接受的都不知道，可以通过并行运行（无论是通过线程还是交替计算）不同索引的 takes_a_long_time 计算，直到其中一个完成。再次强调，这并不保证在计算上是可行的——如果你计算机内存能容纳的每个索引都需要至少十亿年，你在实践中就会陷入困境，尽管理论上你有解决方案。

Answer 2

从问题的评论来看，这个曲线表现得很好，你可以使用类似于三分查找的方法。唯一的问题是，当你接近零的时候，可能会遇到一些麻烦。所以不要从零开始：可以定义一个新的函数g，这个函数是从你的函数f变换过来的，形式是g(x) = f(1/x)。然后从x=0和一个小值开始搜索，逐渐加大区间的大小，直到找到最小值。

为了做到这一点，你需要知道当f的输入值趋近于无穷大时的极限，或者等价地，g的输入值趋近于零时的极限。如果这个极限不能明确计算出来，我建议你尝试数值近似的方法。

可以查看答案的评论，那里有一些关于如何增大区间大小的建议，特别是Steve Jessop提到的那些。