まえがき:
先ほど二分探索法を紹介しましたが、考えてみましょう。なぜ二分探索法を半分に折らなければならないのでしょうか?四つ折り以上に折りたたむのではなく?
例えば、英語の辞書で「apple」を調べるとき、辞書を開いたときに無意識のうちに表紙を見たり裏ページを見たりしませんか? 「zoo」をもう一度チェックする場合、どのようにチェックしますか?もちろん辞書の真ん中から調べ始めるのではなく、ある目的を持って前や後ろに目を向けます。
同様に、たとえば、0 ~ 10000 の値の範囲で小さい値から大きい値まで均一に分散された 100 個の要素を持つ配列で 5 を見つけたい場合、当然、配列の小さい添字を最初に考慮して検索を開始します。
上記の分析は、実際には二分探索を改良した補間探索のアイデアです。
基本的な考え方:
この検索方法は、検索対象のキーワード キーと、ルックアップ テーブル内の最大および最小のレコードのキーワードを比較することに基づいています。検索方法の核心は、補間計算式
$key にあります。 - $arr[$low]
——————————-
$arr[$high] - $arr[$low]
コード:
<?php //插值查找(前提是数组必须是有序数组) 事件复杂度 O(logn) //但对于数组长度比较大,关键字分布又是比较均匀的来说,插值查找的效率比折半查找的效率高 $i = 0; //存储对比的次数 //@param 待查找数组 //@param 待搜索的数字 function insertsearch($arr,$num){ $count = count($arr); $lower = 0; $high = $count - 1; global $i; while($lower <= $high){ $i ++; //计数器 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;
概要:
時間計算量から観点から見ると、これも O(logn ) ですが、比較的長い順序付けされたリストと比較的均等にキーワードが分布しているルックアップ テーブルの場合、内挿検索アルゴリズムの平均パフォーマンスはバイナリ検索よりもはるかに優れています。逆に、配列内の分布が {0, 1, 2, 2000, 2001,. 。 。 999998, 999999} この種の非常に不均一なデータでは、内挿検索の使用はあまり適切な選択ではない可能性があります。
上記は PHP 順序付きテーブル検索 ---- 補間検索の内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) をご覧ください。