検索アルゴリズム

PHP の二分探索を理解する

二分探索は、ソートされた配列内の要素を見つけるためのより効率的なアルゴリズムです。これは、検索間隔を繰り返し半分に分割することで機能します。 binarySearch 関数の詳細な内訳は次のとおりです:

function binarySearch(array $arr, float|int $x)
{
    $low = 0;
    $high = count($arr)-1;
    // $midIndex = (int) ($low + ($high - $low)/2);
    $i = 0;
    while($low <= $high){
        $i++;
        $midIndex = (int) ($low + (($high - $low)/2)); //the same as  intdiv($low + $high, 2);

        if($arr[$midIndex] == $x){
            return "The number {$x} was found in index {$midIndex} of the array. The number of iteration was {$i}";
        }elseif($x > $arr[$midIndex]){
            $low = $midIndex +1;
            echo $low."\n";
        }else{
            $high = $midIndex - 1;
        }
    }

return "The number {$x} was not found in the array";


}

echo binarySearch([1,2,3,4,5,6,7,8,9,10,44,45,46,47,48,49,50], 45)

関数 binarySearch は 2 つのパラメータを受け入れます:

1. $arr: ソートされた整数の配列。
2. $x: 検索する数値。浮動小数点または整数を指定できます。
3. $low は配列の最初のインデックスに初期化されます。
4. $high は配列の最後のインデックスに初期化されます。
5. $i は反復回数を追跡するためのカウンターです。
6. while ループは、検索間隔が有効である限り実行されます ($low が $high 以下である)。
7. $midIndex は、現在の間隔の中間インデックスとして計算されます。
8. 中央の要素が $x に等しい場合、関数はインデックスと反復回数を返します。
9. $x が中央の要素より大きい場合は、$low をmidIndex + 1 に調整します (検索を上半分に絞り込みます)。
10. $x が中央の要素より小さい場合は、$high をmidIndex - 1 に調整します (検索を下半分に絞り込みます)。

PHP の線形検索を理解する

線形検索は、配列内の特定の要素を見つけるために使用される最も単純な検索アルゴリズムの 1 つです。 PHP の LinearSearch 関数を詳しく見てみましょう。

function linearSearch(array $arr, float|int $x)
{
    for($i=0; $i < count($arr); $i++){
        if($x === $arr[$i]){
            return "The number {$x} was found in index {$i} of the array\n";
        }
    }

    return "The number {$x} was not found in the array\n";
}

echo linearSearch([1,5,6,3,4,11,3,2], 4);

関数 LinearSearch は 2 つのパラメータを受け入れます:

1. $arr: 整数の配列。
2. $x: 検索する数値。浮動小数点または整数を指定できます。
3. for ループは配列の各要素を反復処理します。 count($arr) 関数は、配列内の要素の数を返します。
4. ループ内で、コードは現在の要素 ($arr[$i]) が $x と等しいかどうかをチェックします。一致するものが見つかった場合は、その番号が見つかったインデックスを示すメッセージを返します。
5. 数値が見つからないままループが完了した場合、関数は配列内で数値が見つからなかったことを示すメッセージを返します。
6. 線形検索は単純で実装が簡単です。目的の要素が見つかるか、配列の末尾に到達するまで、配列の各要素を順番にチェックします。このアプローチはシンプルですが、時間計算量が O(n) であるため、大規模な配列の場合は非効率的になる可能性があります。

以上が検索アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。