[科普中國(guó)]-插值查找

插值查找，有序表的一種查找方式。插值查找是根據(jù)查找關(guān)鍵子與查找表中最大最小記錄關(guān)鍵字比較后的查找方法。插值查找基于二分查找，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，提高查找效率。

基本思想查找( Search)是指從一批記錄中找出滿足指定條件的某一記錄的過(guò)程，查找又稱(chēng)為檢索。查找算法廣泛應(yīng)用于各類(lèi)應(yīng)用程序中。因此，一個(gè)有效的查找算法往往可以大大提高程序的執(zhí)行效率。在實(shí)際應(yīng)用中，數(shù)據(jù)的類(lèi)型千變?nèi)f化，每條數(shù)據(jù)項(xiàng)往往包含多個(gè)數(shù)據(jù)域。但是，在執(zhí)行查找操作時(shí)，往往只是指定一個(gè)或幾個(gè)域的值，這些作為查找條件的域稱(chēng)為關(guān)鍵字(Key)，關(guān)鍵字分為兩類(lèi)。

我們遇到的大部分查找問(wèn)題都是以主關(guān)鍵字為準(zhǔn)的。而且為了方便讀者的理解，后面將以整型數(shù)據(jù)關(guān)鍵字為例進(jìn)行講解，其他類(lèi)型的關(guān)鍵字的查找算法與此類(lèi)似。如果查找到相應(yīng)的數(shù)據(jù)項(xiàng)，往往需要返回該數(shù)據(jù)項(xiàng)的地址或者位置信息。這樣程序中即可通過(guò)位置信息來(lái)進(jìn)行顯示數(shù)據(jù)項(xiàng)、插入數(shù)據(jù)項(xiàng)、刪除數(shù)據(jù)項(xiàng)等操作。如果沒(méi)有查找到相應(yīng)的數(shù)據(jù)項(xiàng)，則可以返回相應(yīng)的提示信息。

在實(shí)際應(yīng)用中，針對(duì)不同的情況往往可以選擇不同的查找算法。對(duì)于無(wú)順序的數(shù)據(jù)，只有逐個(gè)比較數(shù)據(jù)，才能找到需要的內(nèi)容，這種方法稱(chēng)為順序查找。對(duì)于有順序的數(shù)據(jù)，也可以采用順序查找法逐個(gè)比較，但也可以采取其他更快速的方法找到所需數(shù)據(jù)。另外，對(duì)于一些特殊的數(shù)據(jù)結(jié)構(gòu)，例如鏈表、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)等，也都有相對(duì)應(yīng)的合適的查找算法。1

插值類(lèi)似于平常查英文字典的方法，在查一個(gè)以字母C開(kāi)頭的英文單詞時(shí)，決不會(huì)用二分查找，從字典的中間一頁(yè)開(kāi)始，因?yàn)橹浪拇蟾盼恢檬窃谧值涞妮^前面的部分，因此可以從前面的某處查起，這就是插值查找的基本思想。

插值查找除要求查找表是順序存儲(chǔ)的有序表外，還要求數(shù)據(jù)元素的關(guān)鍵字在查找表中均勻分布，這樣，就可以按比例插值。2

性能分析插值查找性能分析：算法在最好和最壞情況下的關(guān)鍵字比較次數(shù)是明顯的，但平均情況的分析比較復(fù)雜，并且這里的“平均”與前面討論過(guò)的查找算法的平均不同，這里是在元素滿足某種分布情況下的平均。3

適用條件適合于關(guān)鍵字值分布均勻的集合。

應(yīng)用根據(jù)關(guān)鍵字的分布估計(jì)被查元素的位置，能更精確定位到被查找元素的位置，但應(yīng)用有限。4

其他查找算法分塊查找若查找表中的數(shù)據(jù)元素的關(guān)鍵字是按塊有序的，則可以做分塊查找。分塊查找又稱(chēng)索引順序查找，是對(duì)順序查找的一種改進(jìn)。分塊查找將查找表按塊分成若干個(gè)子表，對(duì)每個(gè)子表建立一個(gè)索引項(xiàng)，再將這些索引項(xiàng)順序存儲(chǔ)，形成一個(gè)索引表。每個(gè)索引項(xiàng)包括兩個(gè)字段：關(guān)鍵碼字段（存放對(duì)應(yīng)子表中的最大關(guān)鍵碼值）和指針字段（存放指向?qū)?yīng)子表的指針），這樣索引表則是按關(guān)鍵碼有序的。查找時(shí)，分成兩步進(jìn)行：先根據(jù)給定值kx在索引表中查找，以確定所要查找的數(shù)據(jù)元素屬于查找表中的哪一塊，由于索引表按關(guān)鍵碼有序，因此可用順序查找或折半查找；然后，再進(jìn)行塊內(nèi)查找，因?yàn)閴K內(nèi)無(wú)序，只能進(jìn)行順序查找。2

順序查找順序查找比較簡(jiǎn)單，執(zhí)行的操作是從數(shù)據(jù)序列中的第1個(gè)元素開(kāi)始，從頭到尾依次逐個(gè)查找，直到找到所需要的數(shù)據(jù)或搜索整個(gè)數(shù)據(jù)序列。順序查找主要針對(duì)數(shù)量較少的、無(wú)規(guī)則的數(shù)據(jù)。對(duì)于包含n個(gè)數(shù)據(jù)的數(shù)據(jù)序列，使用順序查找方法查找數(shù)據(jù)，最理想的情況是目標(biāo)數(shù)據(jù)位于數(shù)組的第1個(gè)，這樣比較1次就能找到目標(biāo)數(shù)據(jù);而最差的情況是需要比較完所有的n個(gè)數(shù)據(jù)才能找到目標(biāo)數(shù)據(jù)或者確認(rèn)沒(méi)有該數(shù)據(jù)。平均來(lái)說(shuō)，使用順序查找方法比較次數(shù)為n2次，效率是比較低的。1

本詞條內(nèi)容貢獻(xiàn)者為:

徐恒山 - 講師 - 西北農(nóng)林科技大學(xué)