jfe*_*ard 11
这两种算法都在有序的元素列表中搜索值，但它们解决了不同的问题。指数搜索是为无界列表明确设计的，而二分搜索则是针对有界列表。
指数搜索背后的想法非常简单：搜索边界，然后执行二分搜索。
让我们举个例子。A = [1, 3, 7, 8, 10, 11, 12, 15, 19, 21, 22, 23, 29, 31, 37]. 这个列表可以看作是一棵二叉树（虽然不需要构建树）：
15
____/ \____
/ \
__8__ _23__
/ \ / \
3 11 21 31
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
对e = 27（例如）的二分搜索将经历以下步骤
b0) 设T, R分别为树及其根
15 (R)
____/ \____
/ \
__8__ _23__
/ \ / \
3 11 21 31
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
B1）比较e，以R：e > 15。让分别T, R是T右子树和它的根
15
____/ \____
/ \
__8__ _23_(R)
/ \ / \
3 11 21 31
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
B2）进行比较e来R：e > 23。让分别T, R是T右子树和它的根
15
____/ \____
/ \
__8__ _23__
/ \ / \
3 11 21 31 (R)
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
B3）比较e来R：e < 31。让我们T, R来T分别左子树和它的根
15
____/ \____
/ \
__8__ _23__
/ \ / \
3 11 21 31___
/ \ / \ / \ / \
1 7 10 12 19 22 29 (R) 37
B4）比较e到R：e <> 29：该元素是不是在列表中，因为T没有树。
指数搜索e = 27（例如）将经历以下步骤
让T, R是最左边的子树（即，叶1）和其根（1分别）
15
____/ \____
/ \
__8__ _23__
/ \ / \
3 11 21 31
/ \ / \ / \ / \
(R) 1 7 10 12 19 22 29 37
E1）比较e来R：e > 1。我们R是母公司R和T是具有树R的根
15
____/ \____
/ \
__8__ _23__
/ \ / \
(R) 3 11 21 31 (R)
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
E2）进行比较e来R：e > 3。我们R是母公司R和T是具有树R的根目录：
15
____/ \____
/ \
(R)_8__ _23__
/ \ / \
3 11 21 31 (R)
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
E3）进行比较e来R：e > 8。我们R是母公司R和T是具有树R的根目录：
(R) 15
____/ \____
/ \
__8__ _23__
/ \ / \
3 11 21 31 (R)
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
E4）比较e来R：e > 15。R没有父母。让T成为 的右子树T并R成为它的根：
15
____/ \____
/ \
__8__ _23_(R)
/ \ / \
3 11 21 31
/ \ / \ / \ / \
1 7 10 12 19 22 29 37
e5..7) 见步骤 b2..4)
为了演示起见，让N = 2^n是 的大小，A让索引从 开始1。如果N不是二的幂，结果几乎一样。
让0 <= i <= n成为最小值，使得A[2^(i-1)] < e <= A[2^i](let A[2^-1] = -inf)。请注意，如果您有重复的值，这种间隔可能不是唯一的，因此是“最小值”。
您需要i + 1迭代才能找到i. （在这个例子中，你反复从孩子跳到父母，直到你发现父母大于e或没有更多的父母）
然后在选定的时间间隔上使用二分搜索。这个区间的大小是2^i - 2^(i-1) = 2^(i-1)。
在尺寸数组的二进制搜索的成本2^k是可变的：你可能会在第一次迭代中找到该值，或之后k的迭代（还有取决于元素的分布复杂的分析，但基本上，这是间1和k迭代，你可以事先不知道）
j_i, 1 <= j_i <= i - 1在我们的例子中，让是二分搜索所需的迭代次数（这个间隔的大小是2^(i-1)）。
让i成为最小值，以便A[2^(i-1)] < e <= A[2^i]。由于假设N = 2^n，二分查找将满足这个区间：
我们从根开始A[2^(n-1)]。如果e > A[2^(n-1)]，i = n因为R = A[2^(n-1)] < e < A[2^n]。否则，我们有e <= A[2^(n-1)]. 如果e > A[2^(n-2)]，那么i = n-1，否则我们继续直到我们找到i。
您需要使用二进制搜索n - i + 1进行查找的步骤i：
i = n，您在第一次迭代时就知道 ( e > R) else，您选择左子树i = n-1，你需要两次迭代i = 0，您将需要n迭代。然后您将需要j_i如上所示的迭代来完成搜索。
如您所见，这j_i两种算法的迭代都是通用的。问题是：是i + 1 < n - i + 1吗？即是i < n - i或2i < n？如果是，指数搜索将比二分搜索快。如果不是，二分搜索将比指数搜索快（或同样快）
让我们得到一些距离：2i < n相当于(2^i)^2 < 2^nor 2^i < sqrt(2^n)。而2^i < sqrt(N)，指数搜索速度更快。只要2^i > sqrt(N)，二分查找就会更快。请记住， 的索引e低于或等于2^i因为e <= A[2^i]。
简单来说，如果你有N元素并且如果e在第一个sqrt(N)元素中，那么指数搜索会更快，否则二分搜索会更快。
这取决于分布，但是N - sqrt(N) > sqrt(N)如果N > 4，因此二进制搜索可能比指数搜索更快，除非您知道元素将在第一个元素中或者列表非常短。
2^n < N < 2^(n+1)我不会详细介绍，但这不会改变一般结论。
如果该值超出了 2 的最后一次幂，则指数找到边界的成本已经n+2超过了二分查找（小于或等于2^(n+1)）。然后你有一个二分搜索要执行，也许在一个很小的时间间隔内，但二分搜索已经是赢家。
否则，您将值添加A[N]到列表中，直到您2^(n+1)有价值为止。这不会改变指数搜索的任何内容，这会减慢二进制搜索的速度。但是如果e不是在第一个sqrt(2^(n+1))值中，这种缓慢的二进制搜索仍然更快。
这是一个有趣的问题，我不讨论，指针的大小之类的东西。如果您正在执行指数搜索并在元素到达时使用它们（想象时间戳），您不需要一次存储整个列表。您只需要存储一个元素（第一个），然后是一个元素（第二个），然后是两个元素（第三个和第四个），然后是四个元素，......然后是2^(i-1)元素。如果i很小，那么您将不需要像常规二分搜索那样存储大列表。
实现在这里真的不是问题。有关信息，请参阅 Wikipedia 页面：二元搜索算法和指数搜索。
仅当序列是无界的或当您知道该值可能是第一个时才使用指数搜索。无界：我喜欢时间戳的例子：它们正在严格增长。您可以想象一个存储时间戳的服务器。您可以要求n 时间戳，并且您正在寻找特定的时间戳。询问 1，然后是 2，然后是 4，然后是 8，...时间戳，并在一个时间戳超过您要查找的值时执行二进制搜索。
在其他情况下，使用二分查找。
备注：指数搜索的第一部分背后的思想有一些应用：
| 归档时间： |
|
| 查看次数： |
5097 次 |
| 最近记录： |