PHPで二分探索アルゴリズムを実装する方法

この記事では、主に PHP 二分探索アルゴリズムの実装方法を紹介し、二分探索アルゴリズムの原理を簡単に分析し、具体的な例を組み合わせて、PHP がループと再帰に基づいて二分探索を実装するために必要な操作スキルを提供します。この記事へ

この記事では、PHPの二分探索アルゴリズムの実装方法について説明します。参考のために皆さんと共有してください。詳細は次のとおりです。

二分探索法では、配列が順序付けられた配列である必要があります

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

1. 中間位置については、開始位置と終了位置を把握し、中間位置の値を取得して私たちの値と比較する必要があります。

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

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 サイトの他の関連記事を参照してください。