我最近遇到了一种在排序列表中搜索数字的算法，它是这样进行的:
Given:一个 oracle，告诉您给定数字是否大于或小于要搜索的数字。
从列表中的第一个元素开始。向前跳过 1 个元素，并询问 oracle 是否已经领先于正在搜索的数字。
如果没有，请跳过 2 个元素并询问 oracle 是否你走得太远了。
如果不跳过前面的 4 个元素，等等......
当您找到导致您跳过正在搜索的数字的第一个跳过时，您可以确定包含正在搜索的数字的子区间。
最后对子区间进行二分查找。
我想知道这个算法叫什么，以便我可以对它做更多的研究。
谢谢
最佳答案
这就是您对无限集进行二分搜索的方式。
例如，求解不等式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
关于algorithm - 这个搜索算法叫什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16750946/