插值查找，有序表的一種查找方式。插值查找是根據查找關鍵字與查找表中最大最小記錄關鍵字比較後的查找方法。插值查找基於二分查找，將查找點的選擇改進為自適應選擇，提高查找效率。
基本介紹
- 中文名：插值查找
- 外文名：Interpolation Search
- 性質：通信信息科學術語
基本思想,性能分析,適用條件,套用,其他查找算法,分塊查找,順序查找,
基本思想
查找( Search)是指從一批記錄中找出滿足指定條件的某一記錄的過程，查找又稱為檢索。查找算法廣泛套用於各類應用程式中。因此，一個有效的查找算法往往可以大大提高程式的執行效率。在實際套用中，數據的類型千變萬化，每條數據項往往包含多個數據域。但是，在執行查找操作時，往往只是指定一個或幾個域的值，這些作為查找條件的域稱為關鍵字(Key)，關鍵字分為兩類。
我們遇到的大部分查找問題都是以主關鍵字為準的。而且為了方便讀者的理解，後面將以整型數據關鍵字為例進行講解，其他類型的關鍵字的查找算法與此類似。如果查找到相應的數據項，往往需要返回該數據項的地址或者位置信息。這樣程式中即可通過位置信息來進行顯示數據項、插入數據項、刪除數據項等操作。如果沒有查找到相應的數據項，則可以返回相應的提示信息。
在實際套用中，針對不同的情況往往可以選擇不同的查找算法。對於無順序的數據，只有逐個比較數據，才能找到需要的內容，這種方法稱為順序查找。對於有順序的數據，也可以採用順序查找法逐個比較，但也可以採取其他更快速的方法找到所需數據。另外，對於一些特殊的數據結構，例如鍊表、樹結構和圖結構等，也都有相對應的合適的查找算法。
插值類似於平常查英文字典的方法，在查一個以字母C開頭的英文單詞時，決不會用二分查找，從字典的中間一頁開始，因為知道它的大概位置是在字典的較前面的部分，因此可以從前面的某處查起，這就是插值查找的基本思想。
插值查找除要求查找表是順序存儲的有序表外，還要求數據元素的關鍵字在查找表中均勻分布，這樣，就可以按比例插值。
性能分析
插值查找性能分析：算法在最好和最壞情況下的關鍵字比較次數是明顯的，但平均情況的分析比較複雜，並且這裡的“平均”與前面討論過的查找算法的平均不同，這裡是在元素滿足某種分布情況下的平均。
適用條件
適合於關鍵字值分布均勻的集合。
套用
根據關鍵字的分布估計被查元素的位置，能更精確定位到被查找元素的位置，但套用有限。
其他查找算法
分塊查找
若查找表中的數據元素的關鍵字是按塊有序的，則可以做分塊查找。分塊查找又稱索引順序查找，是對順序查找的一種改進。分塊查找將查找表按塊分成若干個子表，對每個子表建立一個索引項，再將這些索引項順序存儲，形成一個索引表。每個索引項包括兩個欄位：關鍵碼欄位（存放對應子表中的最大關鍵碼值）和指針欄位（存放指向對應子表的指針），這樣索引表則是按關鍵碼有序的。查找時，分成兩步進行：先根據給定值kx在索引表中查找，以確定所要查找的數據元素屬於查找表中的哪一塊，由於索引表按關鍵碼有序，因此可用順序查找或折半查找；然後，再進行塊內查找，因為塊內無序，只能進行順序查找。
順序查找
順序查找比較簡單，執行的操作是從數據序列中的第1個元素開始，從頭到尾依次逐個查找，直到找到所需要的數據或搜尋整個數據序列。順序查找主要針對數量較少的、無規則的數據。對於包含n個數據的數據序列，使用順序查找方法查找數據，最理想的情況是目標數據位於數組的第1個，這樣比較1次就能找到目標數據;而最差的情況是需要比較完所有的n個數據才能找到目標數據或者確認沒有該數據。平均來說，使用順序查找方法比較次數為n次，效率是比較低的。
