PHP に関する簡単な説明パート 3 --- 二分探索メソッドを使用して array_PHP チュートリアルで要素の位置を見つける
- WBOYオリジナル
- 2016-07-13 17:50:14998ブラウズ
PHP では、array_search() 関数を使用して、配列内の要素値のキー名を見つけることができます。
同様に、バイナリメソッドを使用して、配列内の要素のキー名を見つけることができます。
では、二分法とは何でしょうか?
説明しましょう:
データが昇順でソートされている場合、指定された値が現在の位置の値と完全に等しい場合、検索は成功します。現在の位置の場合は、現在の値に基づいて前半の値を検索します。逆に、指定された値が現在の値より大きい場合は、その値に基づいて後半の値を検索します。現在の値について。
言い換えれば、バイナリメソッドを使用して検索されたデータはソートされなければなりません。
以下では、配列 array (1,2,3,4,5,6,7,8,9,10) 内の特定の値の位置を見つけようとします:
関数検索($a,$val){
$low = 0;
$high= count($a) - 1;
while($low
$mid = intval(($low+$high)/2);
if($a[$mid] == $val)
$mid を返します;
if($a[$mid] > $val){
$high = $mid - 1;
}その他{
$low = $mid + 1;
}
}
-1 を返します;
}
?>
上記の関数の場合、最初のパラメーターは配列で渡される値であり、2 番目のパラメーターは配列に対してクエリされる値です。
配列のキーの最小値 $low を 0 に設定し、最大値 $high を配列の長さから 1 を引いた値に設定します。その後、中間値を intval(($low+$height) に設定できます。 /2)、
つまり、配列要素の長さが奇数の場合、配列の中央の値はちょうど中央になります。
たとえば、配列の長さが 5 の場合、中央の値はちょうど 2、つまり (0+4)/2 になります
0,1,2,3,4
そして、配列の長さが偶数の場合、上記の式では割り切れないので、加算法による丸めか四捨五入法による丸めをする必要があります
たとえば、配列の長さが 6 で、中央の値が (0+5)/2 で、その値が 2.5 の場合、配列内のキー 2.5 は存在しないため、2 に丸める必要があります
0,1,2,3,4,5
上記の丸め関数 intval や Floor 関数を使用した場合、取得されるキーは 2 です。 ceil 丸めを使用した場合、ここで取得されるキーは 3 です
それでは、上記の配列を例として見てみましょう:
配列の長さは 10 で、中間値は intval((0+(10-1))/2)、つまり 4 です。4 のインデックスは配列の 5 番目の要素「5」です
1,2,3,4,5,6,7,8,9,10
さて、次は審査を始めましょう
1. クエリ対象の値がたまたま「5」であった場合、検索は成功し、値のインデックスを直接返すことができます。
それは
if($a[$mid] == $val)
$mid を返します;
2. クエリする値が「5」未満の場合、$high の値を中央の値から 1 を引いた値 (4-1) に設定し、中央の前半 (赤い部分) に戻る必要があります。クエリを続行するための値
1,2,3,4,5,6,7,8,9,10
つまり:
if($a[$mid] > $val){
$high = $mid - 1;
}
3. クエリする値が「5」より大きい場合、$low の値を中央の値に 1 を加えた値 (4+1) に設定し、戻って後半 (赤い部分) のクエリを続行する必要があります。 ) 中間値
1,2,3,4,5,6,7,8,9,10
つまり:
他{
$low = $mid + 1;
}
設定後、$low<=$high の条件が満たされると、クエリはこの条件が満たされなくなるまで繰り返されます。つまり、クエリされる範囲が 1 つの配列要素未満になるまで繰り返されます。クエリする値が配列に存在しないと言われました。戻り値は -1
です。
while($low
......
}
-1 を返します;
この関数の欠点は次のとおりです:
配列内に重複した値がある場合、いずれかの値のキーのみが見つかります。興味がある場合は、上記の関数を改善して返信を残すことができます。
zdrjlamp より抜粋