我最近遇到了一种在排序列表中搜索数字的算法，它是这样的：
给定：一个预言机，它告诉您给定的数字是否大于或小于正在搜索的数字。
从列表中的第一个元素开始。向前跳过 1 个元素并询问预言机您是否已经超过了正在搜索的数字。
如果没有，请跳过 2 个元素并询问神谕您是否走得太远。
如果不跳过前面的 4 个元素，等等......
当您找到导致您忽略正在搜索的号码的第一个跳过时，您可以确定包含正在搜索的号码的子区间。
最后，对子区间进行二分查找。
我想知道这个算法叫什么，以便我可以对它做更多的研究。
谢谢
问问题
189 次
3 回答
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
于 2013-05-25T15:32:05.137 回答
0
我建议对算法进行一些更改。应该有 2 个迭代器一个接一个，当你意识到你已经移动到一个列表节点，该节点的数量大于被搜索的数量时..我们应该使用前一个迭代器重新开始相同的步骤..这一直持续到我们找到数字..因为我不明白如何在 log(N) 时间内使用列表进行二进制搜索...
于 2013-05-25T20:38:38.523 回答
0
这种数据结构称为跳过列表
跳过列表是一种数据结构，用于使用链接列表的层次结构存储已排序的项目列表，这些链接列表连接项目的越来越稀疏的子序列。这些辅助列表允许以与平衡二叉搜索树相当的效率进行项目查找（即，探测器的数量与 log n 而不是 n 成正比）。
于 2013-05-25T15:22:46.213 回答