Exemple d'explication de l'implémentation PHP de la fonction de recherche de tableau basée sur la dichotomie-tutoriel php-php.cn

Exemple d'explication de l'implémentation PHP de la fonction de recherche de tableau basée sur la dichotomie

jacklove

Libérer： 2023-04-02 18:36:01

original

1494 Les gens l'ont consulté

Cet article présente principalement PHP pour implémenter la fonction de recherche de tableau basée sur la méthode binaire. Il analyse les techniques d'implémentation associées de la boucle while et de l'algorithme d'appel récursif pour implémenter la fonction de recherche binaire sous forme d'exemples. à cela

L'exemple de cet article décrit comment PHP implémente la fonction de recherche de tableau basée sur la méthode binaire. En le partageant avec tout le monde pour votre référence, les détails sont les suivants :

Dichotomie. Utilisez respectivement la méthode de boucle while et la méthode d'appel récursif.

<?php
// 二分法的使用数组必须是有序的，或升序，或降序
$arr = array(
  1, 3, 5, 7, 9, 13
);
// 递归调用（相比较好理解
function bsearch_r($v, $arr, $low, $high){
  if ($low > $high) {// 先判断结束条件
    return -1;
  }
  $i = intval(($high + $low)/2);
  if ($arr[$i] > $v){
    return bsearch_r($v, $arr, $low, $i-1);// 递归
  } else if ($arr[$i] < $v){
    return bsearch_r($v, $arr, $i+1, $high);
  } else {
    return $i;
  }
}
echo bsearch_r(1, $arr, 0, count($arr)-1);// 0
echo &#39;<hr/>&#39;;
echo bsearch_r(14, $arr, 0, count($arr)-1);// -1
echo &#39;<hr/>&#39;;
// while循环
function bsearch($v, $arr){
  $low = 0;
  $high = count($arr)-1;// 使用下标，注意减去1
  // 注意凡是使用到while的时候，一定要防备无限循环的时候，注意终止循环的判断。
  while($low <= $high){// 比如$low<=$high，这个等于号必须有。
    $i = intval(($high + $low)/2);
    if ($arr[$i] > $v){
      $high = $i-1;
    } else if ($arr[$i] < $v){
      $low = $i+1;
    } else {
      return $i;
    }
  }
  return -1;// 找不到的时候返回-1
}
echo bsearch(13, $arr);// 5
echo &#39;<hr/>&#39;;
echo bsearch(14, $arr);// -1

Copier après la connexion

Résultats d'exécution :