PHP を使用して二分探索アルゴリズムのコード共有を実装する_PHP チュートリアル-PHPチュートリアル-php.cn

PHP を使用して二分探索アルゴリズムのコード共有を実装する_PHP チュートリアル

WBOY

リリース： 2016-07-21 15:28:00

オリジナル

864 人が閲覧しました

最初の方法:
[二分探索の要件]: 1. 順次記憶構造を使用する必要があります。 2. キーワードのサイズに応じて順番に配置する必要があります。
【長所と短所】半減検索法の利点は、比較が少なく、検索速度が速く、平均パフォーマンスが良いことです。欠点は、検索するテーブルが順序付けされたテーブルである必要があり、挿入と削除が難しいことです。。したがって、二分探索法は、頻繁には変更されないが、頻繁に検索される順序付きリストに適しています。
[アルゴリズムの考え方] まず、表の中央に記録されたキーワードと検索キーワードを比較し、一致しない場合は、中央のレコードを使用して表を先頭と最後に分割します。中間位置のレコードが検索キーワードより大きい場合は、前のサブテーブルがさらに検索され、それ以外の場合は、次のサブテーブルがさらに検索されます。

コードをコピーしますコードは次のとおりです:

 
//著者: Distant Expectation
//QQ:15624575 
//ホームページ: http://www.phptogether.com/ 
// 順方向にソートされた配列
$arr=array(1,3,5,7,9,11); 
// 逆方向にソートされた配列
$arr2=array(11,9,7,5,3,1); 
//前方ソートされた配列に対して二分検索を実行します
function searchpart($arr,$x){ 
$start=count($arr)-1; 
while($start<=$end ){ 
$mid=intval(($start+$end)/2);//ここで必要なのは、中央項目の添字の計算値が整数であることを確認することだけです。そうでない場合は、結果に影響を与えずに丸めることができます
if($ arr[$mid ]>$x){//中項目の値がチェック対象の値より大きい場合は、世代差分値が中項目の左側にあることを意味するため、開始します。添字は変更されず、最後の添字は中央項目の添字から 1 を引いたものになります。最初の検索が $arr[0]-$arr[5] の場合、次の検索は 
$end=$mid-1;//$arr[ 0]-$arr[1] 
}elseif($arr [$mid]<$x){//真ん中の項目の値がチェック対象の値より小さい場合、世代差の値がしたがって、最後の添字は変更されず、最初の検索が $arr[0]-$arr[5] の場合、次の / が中央の項目の添字になります。 / 検索は $arr[3]-$arr[5] 
$start=$mid+1; 
}else{// 見つかった場合は、検索する値の添字を返します
return $mid 
} 
} 
 } 
//逆ソートされた配列に対して二分探索を実行します
function searchpart2($arr,$x){ 
$ start=0($arr)-1; 
while($start<=$; end){ 
$mid=intval(($start+$end)/2);//ここで中間を確保する必要があるだけです。項目の添字の計算値は整数にすることも、四捨五入することもできますが、これはそうではありません結果に影響を与える
if($arr[$mid]>$x){//真ん中の項目の値がチェック対象の値より大きい場合、世代差が真ん中にあることを意味しますしたがって、項目の終了添字は変更されず、開始添字は中間項目の添字に 1 を加えたものになります。最初の検索が $arr[0]-$arr[5] の場合、次の検索は 
$start =$mid+ 1;//$arr[3]-$arr[5] 
}elseif($arr[$mid]<$x){//中央の項目の値がチェックする値より小さい場合、世代の違いを意味します。値は中央項目の左側にあります。したがって、開始添字は変更されず、終了添字は中央項目の添字から 1 を引いたものになります。最初の検索が $arr[0]-$arr[5] の場合。 ]、次の / /検索は、 $arr[0]-$arr[1] 
$end=$mid-1; 
}else{// チェックする値の添字を返します
return $ Mid; 
} 
} 
 } 
echo searchpart2($arr,5).'
'; 

 

PHP の二分探索アルゴリズムの実装最近、以前の学習アルゴリズムの知識を整理しました。アルゴリズムは WEB 開発ではほとんど使用されませんが、いくつかの有用なアルゴリズムがまだバックアップされています。 
半探索法は二分探索法とも呼ばれ、要素間の順序関係を利用し、最悪の場合はO(log n)で探索タスクを完了することができます。 。 

【基本的な考え方】
n個の要素をほぼ同じ数で2等分し、a[n/2]と求めたいxを比較し、x=a[n/2]であればxを求め、アルゴリズムは終了します。。 xa[n/2] の場合、配列 a の右半分で x の検索を続けるだけで済みます。二分探索法は非常に広く使われており、その考え方は理解しやすいものです。最初の二分探索アルゴリズムは 1946 年には登場しましたが、最初の完全に正しい二分探索アルゴリズムは 1962 年まで登場しませんでした。 Bentley は著書「Writing Correct Programs」の中で、コンピュータ専門家の 90% は 2 時間以内に完全に正しい二分探索アルゴリズムを書くことができないと書いています。この問題の鍵は、各検索範囲の境界を正確に定式化し、終了条件を決定し、奇数と偶数のさまざまな状況を正確に要約することです。実際、それを整理すると、その特定のアルゴリズムが非常に複雑であることがわかります。直感的。
PHPでの二分探索アルゴリズムの実装

コードをコピー

コードは次のとおりです:

 
/**
* 二分探索アルゴリズム 
* 
* @param array $arr 順序配列 
* @param int $val 検索する値 
* @return int 検索値が存在する場合は配列の添字が返され、存在しない場合は配列の添字が返されます。存在する場合、-1 が返されます 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);//順序付けられた配列の長さを取得する 
$low = 0; = $ l -1; 
while($low { 
$middle = Floor(($low + $high) / 2); 
if($arr[$middle] == $val) 
{ 
$middle を返す 
} 
elseif($arr[$middle] > $val) 
{ 
$high = $middle 
} 
else 
{ 
$low = $middle + 1; } 
 } 
return -1; 
} 
//例 
$arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56,67, 89, 99); 
エコーバイナリ検索($arr,57);