指数搜索

在二进制搜索中，我们要搜索整个列表中的给定关键字。指数搜索通过决定搜索的下限和上限来改进二进制搜索，这样我们就不会搜索整个列表。它能减少我们找到一个元素所需的比较次数。搜索分以下两步进行：

我们通过寻找 2^k 值大于搜索项的第一个指数 k 来确定边界大小。现在，2^k 和 2^k-1 分别成为上限和下限。
对边界 2^k 和 2^k-1 采用二进制搜索算法。

现在让我们使用递归 binarySearch 函数来实现指数搜索：

Unresolved include directive in modules/ROOT/pages/ch08/ch8-04.adoc - include::example$Chapter08/6.php[]

在这里，第一步我们需要 i 个步骤来确定边界。因此，算法的复杂度为 \$O(log i)\$。我们必须记住，这里的 i 比 n 小得多。那么，我们正在进行二进制搜索，边界为 2^j 到 2^j-1，其中 j = \$log i\$。然而，由于我们进行的是较小边界的搜索，我们实际上搜索的是 2^logi \ - 2^logi - 1 = 2^logi-1 的大小。因此，这个边界的复杂度将是 log(2^logi-1) = log (i) - 1 = O(log i)。

因此，指数搜索的复杂度如下：

最好时间复杂度

\$O(1)\$

最坏时间复杂度

\$O(logi)\$

平均时间复杂度

\$O(logi)\$

空间复杂度（最差情况）

\$O(1)\$