理解指數搜索的工作原理

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）執行從開始時的二進制搜索來找到的端

第一步允許定義的大於或等於一個位置搜索範圍爲二進制搜索。由於指數增長因素，其稱爲指數搜索。