理解指数搜索的工作原理

Question

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

编辑（tryd改正我的错误）：

所以我们可以说，我们有数组，我们在数组中搜索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个，然后是第4个，然后是第8个，然后是第16个，依此类推，直到选中元素（数字为2^k）变得大于（或等于）要搜索的值。

在该搜索值这一刻，你知道是在范围2^(k-1)..2^k，并在此范围内

需要注意的是指数级，可找到包含范围内快速地搜索值开始二进制搜索。

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

Answer 2

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

1），用于第一元件比所述值 2）执行从开始时的二进制搜索来找到的端

第一步允许定义的大于或等于一个位置搜索范围为二进制搜索。由于指数增长因素，其称为指数搜索。