Beispielanalyse für den PHP-Halbierungssuchalgorithmus

In diesem Artikel wird hauptsächlich der PHP-Halbsuchalgorithmus (Zweipunktsuchalgorithmus) vorgestellt. Außerdem werden das Konzept, das Prinzip, die Implementierung und die Verwendung des PHP-Halbsuchalgorithmus (Zweipunktsuchalgorithmus) ausführlich analysiert mit einem PHP-Halbsuchalgorithmus (Zweipunkt-Suchalgorithmus) als Referenz, Freunde in Not können darauf verweisen

Dieser Artikel beschreibt den PHP-Halbsuchalgorithmus (Halbierungsalgorithmus) mit Beispielen. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Halbe Abfrage gilt nur für Arrays, Zeichenfolgen usw., die in positiver oder umgekehrter Reihenfolge sortiert wurden;

Algorithmus:

Nehmen Sie zuerst die mittlere Position des Arrays, runden Sie ab;

Falten Sie es von der Mitte aus in zwei Hälften, beurteilen Sie die Größe und Geben Sie die erste Hälfte oder die zweite Hälfte ein;

Und führen Sie dann die gleiche Halb-und-Halb-Abfrage für die erste Hälfte oder die zweite Hälfte durch

wird nicht angehalten, bis das passende Zeichen gefunden wurde (In diesem Beispiel wird Break verwendet. Wenn es in einer Funktion platziert wird, kann Return verwendet werden)

Der von PHP implementierte Code lautet wie folgt:

<?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
*/
?>

Zusätzlich: Suchalgorithmusklasse Halbierung (Halbierung):

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

Diese Situation kann auch auftreten. Die Elemente im Array verfügen über doppelte Daten und das erste in den doppelten Daten muss zurückgegeben werden. Die Position eines Elements, z. B.

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

Bei der Suche nach dem Element 6 sollte die zurückgegebene Position 5 sein, nicht die anderen (der Index beginnt bei 0 zu zählen), daher muss die zurückgegebene Mitte beurteilt werden. Der Code lautet wie folgt:

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

Das obige ist der detaillierte Inhalt vonBeispielanalyse für den PHP-Halbierungssuchalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!