难以理解指数搜索的工作原理

Question

我正在为考试和学习搜索算法而学习。我了解线性、二进制和插值搜索，现在尝试了解指数搜索。但是网上有不好的来源，如果有解释对我来说很复杂..我希望你能澄清算法？

编辑（试图纠正我的错误）：

假设我们有一个数组，我们在数组中搜索 19：

Index i  0  1   2   3    4    5    6
         2  7  13  19   55   92   99

我们先尝试找到范围（在哪个点划分数组）

2^0 : i=1: A[1] > 19
2^1 : i=2: A[2] > 19
2^2 : i=4: A[4] < 19

现在我们知道我们需要从索引 i=0 搜索到 i=3。

现在我们使用二进制搜索来查找元素 19

我们当前的子数组是

Index i  0  1   2   3   
         2  7  13  19

我们在中间划分二分查找，所以我们有数组

13 19

现在再在中间分开。 19 大于 13 并且 19 现在只是数组中的元素。我们完成了，我们找到 19

现在正确吗？

Answer 1

指数搜索是一种用于搜索无限数组或大小未知的数组的算法。它有两个步骤：

1) 查找大于或等于该值的第一个元素的位置 2）从头到尾进行二分查找

第一步允许您定义二进制搜索的范围。并且由于指数增加的因素，它被称为指数搜索。

Answer 2

步骤 应该在搜索的指数阶段增加 。

您必须检查数组的第一个元素，然后是第二个、第四个、第八个、第十六个等等，直到检查的元素（编号为 2^k）变得大于（或等于）值搜索。

此刻你知道搜索到的值在2^(k-1)..2^k范围内，并在这个范围内开始二分查找

请注意，指数阶段允许快速找到包含搜索值的范围。

P.S。对于从零开始的数组计数，检查第 0 个索引很方便，然后开始索引序列 1,2,4,8,16...

Trouble in understanding how Exponential Search works