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

Question

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

给定：一个预言机，它告诉您给定的数字是否大于或小于正在搜索的数字。

从列表中的第一个元素开始。向前跳过 1 个元素并询问预言机您是否已经超过了正在搜索的数字。

如果没有，请跳过 2 个元素并询问神谕您是否走得太远。

如果不跳过前面的 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

Answer 2

我建议对算法进行一些更改。应该有 2 个迭代器一个接一个，当你意识到你已经移动到一个列表节点，该节点的数量大于被搜索的数量时..我们应该使用前一个迭代器重新开始相同的步骤..这一直持续到我们找到数字..因为我不明白如何在 log(N) 时间内使用列表进行二进制搜索...

Answer 3

这种数据结构称为跳过列表

跳过列表是一种数据结构，用于使用链接列表的层次结构存储已排序的项目列表，这些链接列表连接项目的越来越稀疏的子序列。这些辅助列表允许以与平衡二叉搜索树相当的效率进行项目查找（即，探测器的数量与 log n 而不是 n 成正比）。