二进制搜索是否会以除空间复杂度以外的任何方式击败指数搜索？
这两种算法都在元素的有序列表中搜索值，但是它们解决了不同的问题。指数搜索是专门为无边界列表而设计的，而二进制搜索则处理有边界列表。
指数搜索背后的想法非常简单：搜索边界，然后然后执行二进制搜索。
让我们举个例子。 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 37e2）比较
e与R：e > 3。令R为R的父级，令T为以R为根的树：
15 ____/ \____ / \ (R)_8__ _23__ / \ / \ 3 11 21 31 (R) / \ / \ / \ / \ 1 7 10 12 19 22 29 37e3）比较
e与R：e > 8。令R为R的父级，令T为以R为根的树：
(R) 15 ____/ \____ / \ __8__ _23__ / \ / \ 3 11 21 31 (R) / \ / \ / \ / \ 1 7 10 12 19 22 29 37e4）比较
e与R：e > 15。R没有父母。令T为T的右子树，并以R作为其根：
15 ____/ \____ / \ __8__ _23_(R) / \ / \ 3 11 21 31 / \ / \ / \ / \ 1 7 10 12 19 22 29 37e5..7）参见步骤b2..4）
为了演示，让N = 2^n为A的大小，让索引从1开始。如果N不是2的幂，则结果几乎相同。
让0 <= i <= n最小，以便A[2^(i-1)] < e <= A[2^i]（让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），否则，选择左侧子树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^n或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页面：Binary search algorithm和Exponential search。
仅当序列无界或您知道该值可能在第一个序列中时，才使用指数搜索。无界：我喜欢时间戳的示例：它们严格地在增长。您可以想象一个带有存储时间戳的服务器。您可以要求n时间戳，并且正在寻找特定的时间戳。先询问1，然后询问2，然后询问4，然后询问8，...，当一个时间戳超过您要查找的值时，执行二进制搜索。
在其他情况下，使用二进制搜索。
注：指数搜索的第一部分背后的思想有一些应用：