擊敗二分檢索算法——插值檢索、快速檢索

jopen 10年前發布 | 7K 次閱讀算法

英文原文：Beating the binary search algorithm

二分檢索是查找有序數組最簡單然而最有效的算法之一。現在的問題是，更復雜的算法能不能做的更好？我們先看一下其他方法。

有些情況下，散列整個數據集是不可行的，或者要求既查找位置，又查找數據本身。這個時候，用哈希表就不能實現O(1) 的運行時間了。但對有序數組，采用分治法通常可以實現O(log (n))的最壞運行時間。

在下結論前，有一點值得注意，那就是可以從很多方面“擊敗”一個算法：所需的空間，所需的運行時間，對底層數據結構的訪問需求。接下來我們做一個運行時對比實驗，實驗中創建多個不同的隨機數組，其元素個數均在 10,000 到 81,920,000 之間，元素均為 4 字節整型數據。

二分檢索

二分檢索算法的每一步，搜索空間總會減半，因此保證了運行時間。在數組中查找一個特定元素，可以保證在 O(log (n))時間內完成，而且如果找的正好是中間元素就更快了。也就是說，要從 81,920,000 個元素的數組中找某個元素的位置，只需要 27 個甚至更少的迭代。

由于二分檢索的隨機跳躍性，該算法并非緩存友好的，因此只要搜索空間小于特定值（64 或者更少），一些微調的二分檢索算法就會切換回線性檢索繼續查找。然而，這個最終的空間值是極其架構相關的，因此大部分框架都沒有做這個優化。

快速檢索；最后回歸到二分檢索的快速檢索

擊敗二分檢索算法——插值檢索、快速檢索

如果由于某些原因，數組長度未知，快速檢索可以識別初始的搜索域。這個算法從第一個元素開始，一直加倍搜索域的上界，直到這個上界已經大于待查關鍵字。之后，根據實現不同，或者采用標準的二分檢索查找，或者開始另一輪的快速檢索。前者可以保證O(log (n)) 的運行時間，后者則更接近O(n)的運行時間。

如果我們要找的元素比較接近數組的開頭，快速檢索就非常有效。

抽樣檢索

抽樣檢索有點類似二分檢索，不過在確定主要搜索區域之前，它會先從數組中拿幾個樣例。最后，如果范圍足夠小，就采用標準的二分檢索確定待查元素的準確位置。這個理論很有趣，不過在實踐中執行效果并不好。

插值檢索；最后回歸到順序查找的插值檢索

在被測的算法中，插值檢索可以說是“最聰明”的一個算法。它類似于人類使用電話簿的方法，它試圖通過假設元素在數組中均勻分布，來猜測元素的位置。

首先，它抽樣選擇出搜索空間的開頭和結尾，然后猜測元素的位置。算法一直重復這個步驟，直到找到元素。如果猜測是準確的，比較的次數大概是O(log (log (n))，運行時間大概是O(log (n))；但如果猜測的不對，運行時間就會是O(n)了。

插值檢索的一個改進版本是，只要可推測我們猜測的元素位置是接近最終位置的，就開始執行順序查找。相比二分檢索，插值檢索的每次迭代計算代價都很高，因此在最后一步采用順序查找，無需猜測元素位置的復雜計算，很容易就可以從很小的區域（大概 10 個元素）中找到最終的元素位置。

圍繞插值檢索的一大疑問就是，O(log (log (n))的比較次數可能產生O(log (log (n))的運行時間。這并非個案，因為存儲訪問時間和計算下一次猜測的 CPU 時間相比，這兩者之間要有所權衡。如果數據量很大，而且存儲訪問時間也很顯著，比如在一個實際的硬盤上，插值檢索輕松擊敗二分檢索。然而，實驗表明，如果訪問時間很短，比如說 RAM，插值檢索可能不會產生任何好處。

試驗結果

試驗中的源代碼都是用 Java 寫的；每個實驗在相同的數組上運行 10 次；數組是隨機產生的整型數組，存儲在內存中。

在插值檢索中，首先會采用抽樣檢索，從檢索空間拿 20 個樣例，以確定接下來的搜索域。如果假定的域只有 10 個或更少的元素，就開始采用線性檢索。另外，如果這個搜索域元素個數小于 2000，就回退到標準的二分檢索了。

作為參考，java 默認的 Arrays.binarySearch 算法也被加入實驗，以同自定義的算法對比運行時間。

擊敗二分檢索算法——插值檢索、快速檢索

盡管我們對插值檢索期望很高，它的實際運行時間并未擊敗 java 默認的二分檢索算法。如果存儲訪問時間長，結合采用某些類型的哈希樹和B+ 樹可能是一個更好的選擇。但值得注意的是，對均勻分布的數組，組合使用插值檢索和順序檢索在比較次數上總能勝過二分檢索。不過平臺的二分檢索已經很高效，所以很多情況下，可能不需要用更復雜的算法來代替它。

原始數據 – 每個檢索的平均運行時間

擊敗二分檢索算法——插值檢索、快速檢索