本文實例講述了PHP有序表查找之插值查找算法。分享給大家供大家參考，具體如下：
前言：
在前面我們介紹了二分查找，但是我們考慮一下，為什么一定要折半呢？而不是折四分之一或者更多？
打個比方，在英文詞典里查找“apple”，你下意識里翻開詞典是翻前面的書頁還是后面的書頁呢？如果再查“zoo”,你又會怎么查？顯然你不會從詞典中間開始查起，而是有一定目的地往前或往后翻。
同樣，比如要在取值范圍在 0 ~ 10000 之間的100個元素從小到大均勻分布的數(shù)組中查找5，我們自然而然地先考慮數(shù)組下標(biāo)較小的開始查找。
以上的分析其實就是插值查找的思想，它是二分查找的改進(jìn)。
基本思想：
根據(jù)要查找的關(guān)鍵字key與查找表中的最大最小記錄的關(guān)鍵字比較后的查找方法，其核心就在于插值計算公式，我們先看折半查找的計算公式：
而插值查找就是要將其中的 1/2進(jìn)行改進(jìn)，改成下面的計算方案：
插值查找算法的核心就在于插值的計算公式:
$num - $arr[$lower]
—————————————
$arr[$high] - $arr[$lower]
代碼：
<?php//插值查找(前提是數(shù)組必須是有序數(shù)組) 事件復(fù)雜度 O(logn)//但對于數(shù)組長度比較大，關(guān)鍵字分布又是比較均勻的來說，插值查找的效率比折半查找的效率高$i = 0; //存儲對比的次數(shù)//@param 待查找數(shù)組//@param 待搜索的數(shù)字function insertsearch($arr,$num){ $count = count($arr); $lower = 0; $high = $count - 1; global $i; while($lower <= $high){ $i ++; //計數(shù)器 if($arr[$lower] == $num){ return $lower; } if($arr[$high] == $num){ return $high; } // 折半查找 ： $middle = intval(($lower + $high) / 2); $middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower)); if($num < $arr[$middle]){ $high = $middle - 1; }else if($num > $arr[$middle]){ $lower = $middle + 1; }else{ return $middle; } } return -1;}$arr = array(0,1,16,24,35,47,59,62,73,88,99);$pos = insertsearch($arr,62);print($pos);echo "<br>";echo $i;總結(jié)：
從時間復(fù)雜度上來看，它也是 O(logn)，但對于有序表比較長，而關(guān)鍵字分布有比較均勻的查找表來說，插值查找算法的平均性能比二分查找好的多。反之，數(shù)組中如果分布類似于{0，1，2，2000，2001，。。。999998，999999}這種極端不均勻的數(shù)據(jù)，用插值查找未必是很合適的選擇。
我自己特別做了個例子：
$arr = array(0,1,2,2000,2001,2002,2003,2004,5555,69666,99999,100000);echo "位置：".binsearch($arr,5555);echo "<br>";echo "比較次數(shù)：".$i;$i = 0; //重置比較次數(shù)echo "<br>";echo "位置：".insertsearch($arr,5555);echo "<br>";echo "比較次數(shù)：".$i;
結(jié)果輸出：
位置：8比較次數(shù)：2位置：8比較次數(shù)：9
可以得到，對于極端不均勻的數(shù)據(jù)，插值查找效率比折半查找低。
PS：上面提到的binsearch()函數(shù)大家可以參考前面一篇 PHP有序表查找—-二分查找（折半）
希望本文所述對大家PHP程序設(shè)計有所幫助。
新聞熱點
疑難解答
圖片精選
