這個搜索算法叫什麼？

我最近遇到了一個搜索排序列表中的數字的算法，這是怎麼回事：這個搜索算法叫什麼？

鑑於：甲骨文告訴你，如果一個給定的數字大於或小於正在搜索的數字。

從列表中的第一個元素開始。提前跳過1個元素，然後詢問oracle是否超出了要搜索的數字。

如果不是，請跳過2個元素並詢問oracle是否已經太過分了。

如果沒有跳過4個元素提前，等等....

當你找到了導致您正在搜索的傳過來的號碼，你可以確定包含被搜索的數子區間的第一跳。

最後，在子區間上執行二進制搜索。

我想知道這個算法是怎麼調用的，以便我可以對它做更多的研究。

感謝

來源

2013-05-25 user2305684

我可以問爲什麼你會這樣做？在我看來，發現的子區間有50％的可能性只是列表的後半部分，因此可以在二分搜索的一個步驟中找到。 –

[本文]（https://sites.google.com/site/d7013e11/announcements/exponentialbinarysearch）將其稱爲_exponential二進制搜索_。 – hammar

@ImreKerr一個非常好的問題，我可以想象只有一種情況，二進制搜索不適用/更好：當物品數量無限或未知時間。 – delnan

這就是你如何二分搜索一個無界集。

例如，要解決關於正整數的不等式f(n) < t，其中f是遞增函數。

具體的例子：

Solve n**2 + 10*n < 100 over the positive integers. 

Let f(n) = n**2 + 10*n for n > 0 
f is increasing because it's the sum of increasing functions. 

f(1) = 1 + 10 = 11 
f(2) = 4 + 20 = 24 
f(4) = 16 + 40 = 56 
f(8) = 64 + 80 = 144 > 100 

Now we binary search the interval [4,8] 

f(6) = 36 + 60 = 96 
f(7) = 49 + 70 = 119 > 100 

Thus n < 7

來源

2013-05-25 15:32:05

謝謝，這就是我指的！ – user2305684

這個數據結構被稱爲Skip Lists

enter image description here

跳躍列表是用於存儲使用連接日益鏈表的分層次的項的排序列表的數據結構稀疏項目的子序列。這些輔助列表允許項目查找，其效率可與平衡二叉搜索樹（即探針數與logn成比例，而不是n）的平衡二叉搜索樹相比。

來源

2013-05-25 15:22:46

感謝您的回覆，但我並不是指跳過列表。如果我的描述不清楚，我很抱歉。 – user2305684

我建議在算法的一些變化。應該有兩個迭代器，一個接着另一個，當你意識到你已經移動到一個列表節點，它的數量比被搜索的數量更大。我們應該重新啓動與前一個迭代器相同的步驟..這個過程一直持續到我們找到數字..因爲我不明白怎麼會做一個二進制serch即日誌（N）時間與列表...

來源

2013-05-25 20:38:38 sethi

這個搜索算法叫什麼？

回答

相關問題