PHP二分探索の詳しい解説

二分検索は、半検索とも呼ばれ、比較回数が少なく、検索速度が速く、平均パフォーマンスが高いという利点があります。欠点は、検索するテーブルが順序付きテーブルである必要があることと、挿入であることです。削除は難しいです。したがって、二分探索法は、頻繁には変更されないが、頻繁に検索される順序付きリストに適しています。まず、テーブル内の要素が昇順に配置されていると仮定し、テーブルの中央の位置に記録されているキーワードと検索キーワードを比較し、両者が等しい場合は検索が成功します。テーブルを最初と最後の 2 つのサブテーブルに分割します。 If 中央の位置に記録されたキーワードが検索キーワードより大きい場合は、前のサブテーブルがさらに検索され、そうでない場合は次のサブテーブルが検索されます。さらに遠く。条件を満たすレコードが見つかって検索が成功するまで、またはサブテーブルが存在しない場合は検索が失敗するまで、上記のプロセスを繰り返します。

二分探索メソッドでは、配列が順序配列であることが必要です

配列が増加配列であると仮定すると、まず配列の中間位置を見つける必要があります。

1つ。中間位置を知るには、開始位置と終了位置を知ってから、中間位置の値を取得してこの値と比較する必要があります。

2つ。中央の値が指定した値より大きい場合は、この時点で値が中央より前にあることを意味します。中央より前なので、変更する必要がある値は です。このとき、終了位置の値は「We're in the middle at this point」となるはずです。

3つ。一方、中間の値が与えた値より小さい場合は、与えられた値が中間の位置より後であることを意味します。このとき、後半の値は であるため、再度 2 つに分割する必要があります。中間値の後なので、変更する必要がある値は開始位置の値です。指定された値が見つかるまで、この時点の開始位置の値が中間位置になります。

4つ。または、中間値が最初の開始位置または終了位置に等しい場合 (この場合、指定された値が見つかりません)、コードを使用して実装しましょう~

//循环实现
function getValue($num,$arr)
{
//查找数组的中间位置
$length=count($arr);
$start=0;
$end=$length;
$middle=floor(($start+$end)/2);
//循环判断
while($start>$end-1)
{
if($arr[middle]==$num)
{
return middle+1;
}elseif($arr[middle]<$num)
{
//如果当前要查找的值比当前数组的中间值还要打，那么意味着该值在数组的后半段
//所以起始位置变成当前的middle的值，end位置不变。
$start=$middle;
$middle=floor(($start+$end)/2);
}else{
//反之
$end=$middle;
$middle=floor(($start+$end)/2);
}}
return false;
}
 
//递归实现
/*
     * 从数组中获取元素值
     * @param1 int $num，要查找的目标值
     * @param2 array $arr，要查找的数组
     * @param3 int $start，查找的起始位置
     * @param4 int $end，查找的结束位置
     * @return mixed，找到了返回位置，没找到返回false
     */
     function getValue4($num,$arr,$start = 0,$end = 100){
        //采用二分法查找
        $middle = floor(($end + $start) / 2);

        //判断
        if($arr[$middle] == $num){
            //已经找到了，递归的出口
            return $middle + 1;
        }elseif($arr[$middle] < $num){
            //要查找的元素在数组的后半段
            $start = $middle + 1;
            //边界值
            if($start >= $end){
                //没有找到，但是已经超出边界值，递归出口
                return false;
            }
            //调用自己去查找：递归点
            return getValue4($num,$arr,$start,$end);    //getValue4($num,$arr,51,100)
        }else{
            //要查找的元素在数组的前半段
            $end = $middle - 1;
            //判断边界值
            if($end < 0)return false;

            //调用自己：递归点
            return getValue4($num,$arr,$start,$end);    //getValue4($num,$arr,0,49)
        }

        //都没有找到
        return false;
     }

以上がPHP二分探索の詳しい解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。