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

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

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

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

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

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

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