插值查找

基本思想

查找( Search)是指從一批記錄中找出滿足指定條件的某一記錄的過程，查找又稱為檢索。查找算法廣泛套用於各類應用程式中。因此，一個有效的查找算法往往可以大大提高程式的執行效率。在實際套用中，數據的類型千變萬化，每條數據項往往包含多個數據域。但是，在執行查找操作時，往往只是指定一個或幾個域的值，這些作為查找條件的域稱為關鍵字(Key)，關鍵字分為兩類。

我們遇到的大部分查找問題都是以主關鍵字為準的。而且為了方便讀者的理解，後面將以整型數據關鍵字為例進行講解，其他類型的關鍵字的查找算法與此類似。如果查找到相應的數據項，往往需要返回該數據項的地址或者位置信息。這樣程式中即可通過位置信息來進行顯示數據項、插入數據項、刪除數據項等操作。如果沒有查找到相應的數據項，則可以返回相應的提示信息。

在實際套用中，針對不同的情況往往可以選擇不同的查找算法。對於無順序的數據，只有逐個比較數據，才能找到需要的內容，這種方法稱為順序查找。對於有順序的數據，也可以採用順序查找法逐個比較，但也可以採取其他更快速的方法找到所需數據。另外，對於一些特殊的數據結構，例如鍊表、樹結構和圖結構等，也都有相對應的合適的查找算法。

插值類似於平常查英文字典的方法，在查一個以字母C開頭的英文單詞時，決不會用二分查找，從字典的中間一頁開始，因為知道它的大概位置是在字典的較前面的部分，因此可以從前面的某處查起，這就是插值查找的基本思想。

插值查找除要求查找表是順序存儲的有序表外，還要求數據元素的關鍵字在查找表中均勻分布，這樣，就可以按比例插值。

性能分析

插值查找性能分析：算法在最好和最壞情況下的關鍵字比較次數是明顯的，但平均情況的分析比較複雜，並且這裡的“平均”與前面討論過的查找算法的平均不同，這裡是在元素滿足某種分布情況下的平均。

適用條件

適合於關鍵字值分布均勻的集合。

套用

根據關鍵字的分布估計被查元素的位置，能更精確定位到被查找元素的位置，但套用有限。

其他查找算法

分塊查找

若查找表中的數據元素的關鍵字是按塊有序的，則可以做分塊查找。分塊查找又稱索引順序查找，是對順序查找的一種改進。分塊查找將查找表按塊分成若干個子表，對每個子表建立一個索引項，再將這些索引項順序存儲，形成一個索引表。每個索引項包括兩個欄位：關鍵碼欄位（存放對應子表中的最大關鍵碼值）和指針欄位（存放指向對應子表的指針），這樣索引表則是按關鍵碼有序的。查找時，分成兩步進行：先根據給定值kx在索引表中查找，以確定所要查找的數據元素屬於查找表中的哪一塊，由於索引表按關鍵碼有序，因此可用順序查找或折半查找；然後，再進行塊內查找，因為塊內無序，只能進行順序查找。

順序查找

順序查找比較簡單，執行的操作是從數據序列中的第1個元素開始，從頭到尾依次逐個查找，直到找到所需要的數據或搜尋整個數據序列。順序查找主要針對數量較少的、無規則的數據。對於包含n個數據的數據序列，使用順序查找方法查找數據，最理想的情況是目標數據位於數組的第1個，這樣比較1次就能找到目標數據;而最差的情況是需要比較完所有的n個數據才能找到目標數據或者確認沒有該數據。平均來說，使用順序查找方法比較次數為n²次，效率是比較低的。