Ausführliche Erläuterung des Falles des PHP-Halbsuchalgorithmus

Dieses Mal werde ich Ihnen den Fall des PHP-Halbsuchalgorithmus ausführlich erläutern. Was sind die Vorsichtsmaßnahmen bei der Verwendung der PHP-Halbsuche?

Einführung:

Binäre Suche Technologie, auch als Halbsuche bekannt. Seine Voraussetzung ist, dass die Datensätze in der linearen Tabelle in der Schlüsselreihenfolge vorliegen müssen (normalerweise in der Reihenfolge von klein nach groß) und die lineare Tabelle sequentiell gespeichert werden muss.

Grundidee:

Nehmen Sie in einer geordneten Liste den mittleren Datensatz als Vergleichsobjekt. Wenn der angegebene Wert der Schlüssel ist mittlerer Datensatz Wenn sie gleich sind, ist die Suche erfolgreich; wenn der angegebene Wert kleiner als der Schlüssel des mittleren Datensatzes ist, wird die Suche in der linken Hälfte des mittleren Datensatzes fortgesetzt, wenn der angegebene Wert größer als der Schlüssel des mittleren Datensatzes ist Datensatz, wird die Suche in der rechten Hälfte des mittleren Datensatzes fortgesetzt. Wiederholen Sie den obigen Vorgang, bis die Suche erfolgreich ist oder kein Datensatz in allen Suchbereichen vorhanden ist und die Suche fehlschlägt.

Code:

<?php
//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function binsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  $middle = intval(($lower + $high) / 2);
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 //返回-1表示查找失败
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = binsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

Laufergebnis:

7
3

Zusammenfassung:

Die zeitliche Komplexität der binären Suche beträgt O(logn). Da die Voraussetzung für die binäre Suche jedoch die sequentielle Speicherung einer geordneten Tabelle (Array) ist, wird die Aufrechterhaltung der geordneten Sortierung einen erheblichen Arbeitsaufwand mit sich bringen, wenn die geordnete Tabelle häufige Einfüge- oder Löschvorgänge erfordert.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

PHP-Anwendungsfallanalyse für lange Verbindungen

Detaillierte Erläuterung der Containerisierung und Bereitstellung von PHP-Anwendungen

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung des Falles des PHP-Halbsuchalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!