algorithm - 这个搜索算法叫什么？

Question

我最近遇到了一种在排序列表中搜索数字的算法，它是这样进行的:

Given:一个 oracle，告诉您给定数字是否大于或小于要搜索的数字。

从列表中的第一个元素开始。向前跳过 1 个元素，并询问 oracle 是否已经领先于正在搜索的数字。

如果没有，请跳过 2 个元素并询问 oracle 是否你走得太远了。

如果不跳过前面的 4 个元素，等等......

当您找到导致您跳过正在搜索的数字的第一个跳过时，您可以确定包含正在搜索的数字的子区间。

最后对子区间进行二分查找。

我想知道这个算法叫什么，以便我可以对它做更多的研究。

谢谢

Answer 1

这就是您对无限集进行二分搜索的方式。

例如，求解不等式f(n) < t在正整数上，其中 f 是递增函数。

具体例子:

Solve n**2 + 10*n < 100 over the positive integers.

Let f(n) = n**2 + 10*n for n > 0
f is increasing because it's the sum of increasing functions.

f(1) = 1 + 10 = 11
f(2) = 4 + 20 = 24
f(4) = 16 + 40 = 56
f(8) = 64 + 80 = 144 > 100

Now we binary search the interval [4,8]

f(6) = 36 + 60 = 96
f(7) = 49 + 70 = 119 > 100

Thus n < 7