这个搜索算法叫什么名字？

Question

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

给定：一个告诉你一个给定数字大于还是小于正在搜索的数字的Oracle。

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

如果没有，请跳过2个元素并询问Oracle是否已经太远。

若不然，则跳过4个元素......

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

最后，在子间隔上执行二进制搜索。

我想知道这个算法叫什么名字，以便我能够做更多的研究。

谢谢

- user2305684

---

我可以问一下你为什么要这样做吗？在我看来，找到的子区间有50%的可能只是列表的后一半，因此可以在二分搜索的一步中找到。 - Imre Kerr

这篇文章将其称为“指数二分搜索”。 - hammar

@ImreKerr 一个非常好的问题，我只能想象一种情况，二分查找不适用/不是更好的选择：当项目数量是无限的或事先不知道时。 - user395760

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

- Colonel Panic

---

谢谢，这就是我所指的！ - user2305684

Answer 2

这种数据结构被称为跳表

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

- Srikar Appalaraju

---

谢谢回复，但我并不是在提到跳表。如果我的描述不清楚，我很抱歉。 - user2305684

Answer 3

我建议在算法中进行一些更改。应该有两个迭代器，一个跟随另一个，当你意识到你已经移动到一个列表节点，它比正在搜索的数字大时...我们应该使用前一个迭代器重新开始相同的步骤...这样继续进行直到找到数字...因为我不明白如何用log（N）时间在列表中进行二进制搜索...

- sethi