Analyse d'un exemple d'algorithme de recherche PHP à moitié (bisection)

Cet article présente principalement l'algorithme de recherche PHP demi (deux points). Il analyse en détail le concept, le principe, la mise en œuvre et l'utilisation de l'algorithme de recherche PHP demi (deux points). Il est également fourni. avec un algorithme de recherche PHP demi (deux points). ) Classe d'algorithme de recherche pour votre référence, les amis dans le besoin peuvent s'y référer

Cet article décrit l'algorithme de recherche PHP demi (bisection) avec des exemples. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

La demi-requête n'est applicable qu'aux tableaux, chaînes, etc. qui ont été triés dans l'ordre positif ou inverse

Algorithme :

Prenez d'abord la position médiane du tableau, s'il n'y a pas de position médiane, arrondissez vers le bas

Pliez-le en deux à partir du milieu, jugez la taille et ; entrez la première moitié ou la seconde moitié ;

Et puis effectuez la même requête moitié-moitié pour la première moitié ou la seconde moitié

ne s'arrêtera pas tant que le caractère correspondant n'est pas trouvé. (break est utilisé dans cet exemple. S'il est placé dans une fonction, return peut être utilisé)

Le code implémenté par PHP est le suivant :

<?php
$arr = array(1,2,3,4,5,6,7,8,9,10);//数组
$key = 4;//要查询的关键字
$low = 0;//开始位的标志
$high = count($arr);//终止位的标志
while($low <= $high){//查询开始结束的条件
 $mid = floor(($low + $high)/2);//进行中间位置计算，向下取整
 if($arr[$mid] == $key){//查询成功
 echo $arr[$mid];
 break;//结束本页执行，函数可用return
 }elseif($arr[$mid] > $key){ //查询前半段，把结束标志移到中间位置前一位
 $high = $mid - 1;
 }else{ //查询后半段，把开始位置移到中间位置的后一位
 $low = $mid + 1;
 }
}
/*
运行结果：4
*/
?>

Supplémentaire : Classe d'algorithme de recherche de réduction de moitié (bissection) :

/**
 * Description:php实现二分查找算法的类
 * @author wzy
 */
class binary_search{
  public $arr;
  public $key;
  function __construct($arr,$key){
    //这里初始化的数组已经是有序数组
    $this->arr=$arr;
    $this->key=$key;
  }
  function binarysearch(){
    $start=0;
    $end=count($this->arr)-1;
    while($start<=$end){
      //mid的取值可以为上整数或者下整数
      $mid=ceil(($start+$end)/2);
      //$mid=($start+$end)>>1;
      //$mid=intval(($start+$end)/2);
      if($this->arr[$mid]<$this->key){
        $start=$mid+1;
      }else if($this->arr[$mid]>$this->key){
        $end=$mid-1;
      }else{
        return $mid;
      }
    }
  }
}

Vous pouvez également rencontrer cette situation. Les éléments du tableau ont des données en double et les données en double doivent être renvoyées. La position du premier élément dans

.

$arr=array(1,2,3,4,5,6,6,6,6,7,8);

Lors de la recherche de l'élément 6, la position renvoyée doit être 5, pas les autres (l'indice commence à 0 et commence à compter), il doit donc être jugé sur le milieu renvoyé. Le code est tel. suit :

/**
 * Description:php实现二分查找算法的类
 * @author wzy
 */
class binary_search{
  public $arr;
  public $key;
  function __construct($arr,$key){
    //这里初始化的数组已经是有序数组
    $this->arr=$arr;
    $this->key=$key;
  }
  function binarysearch(){
    $start=0;
    $end=count($this->arr)-1;
    while($start<=$end){
      //mid的取值可以为上整数或者下整数
      $mid=ceil(($start+$end)/2);
      //$mid=($start+$end)>>1;
      //$mid=intval(($start+$end)/2);
      if($this->arr[$mid]<$this->key){
        $start=$mid+1;
      }else if($this->arr[$mid]>$this->key){
        $end=$mid-1;
      }else{
        //返回第一个匹配的元素
        for($i=$mid-1;$i>=0;$i--){
          if($this->arr[$i]==$this->key){
            $mid=$i;
          }else{
            break;
          }
        }
        return $mid;
      }
    }
  }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!