Gemeinsame Nutzung des binären PHP-Suchalgorithmus für geordnete Listen (halbe Suche).

In diesem Artikel wird hauptsächlich der binäre Suchalgorithmus (halbe Suche) für die geordnete Tabellensuche in PHP vorgestellt. Er stellt kurz das Konzept und Prinzip der binären Suchmethode vor und analysiert die geordnete lineare Tabellensuche in PHP basierend auf dem binären Suchalgorithmus Die Form von Beispielen kann auf die entsprechenden Bedienfähigkeiten verweisen.

Einführung:

Binäre Suchtechnologie, 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 Datensatzes 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.

Verwandte Empfehlungen:

Beispielanalyse des in PHP implementierten binären Suchalgorithmus

So implementieren Sie den binären Suchalgorithmus in PHP

Beispielcode für die binäre PHP-Suche für rekursive und nicht rekursive Implementierung

Das obige ist der detaillierte Inhalt vonGemeinsame Nutzung des binären PHP-Suchalgorithmus für geordnete Listen (halbe Suche).. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!