PHPで二分探索メソッドを実装する方法

PHP はバイナリ検索メソッドを実装します

バイナリ検索メソッドに必要な配列は、配列が増加する配列であると仮定すると、順序付き配列です。 , まず、配列の中間位置を見つける必要があります。

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

2. 中間の値が指定した値より大きい場合は、中間の位置より前の値であることを意味します。このとき、中間の位置より前なので、再度 2 つに分割する必要があります。したがって、変更する必要がある値は終了位置の値です。このときの終了位置の値は、現時点での中間位置である必要があります。

3. 逆に、中間の値が与えた値より小さい場合は、与えられた値が中間位置より後であることを意味し、このとき後半の値を除算する必要があります。中央の値の後であるため、変更する必要がある値は開始位置の値であり、指定された値が見つかるまでの現時点ではこれが中間位置である必要があります。

4. または、中間値が最初の開始位置または終了位置に等しい (この場合、指定された値が見つかりません)

コードを使用して実装してみましょうそれ

1. ループ実装

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;
}

2. 再帰的実装

/*
     * 从数组中获取元素值
     * @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で二分探索メソッドを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。