Verwendung von PHP zur Implementierung der Codefreigabe für binäre Suchalgorithmen

Die erste Methode:
[Binäre Suchanforderungen]: 1. Es muss eine sequentielle Speicherstruktur verwendet werden. 2. Sie muss entsprechend der Größe der Schlüsselwörter angeordnet werden.
【Vorteile und Nachteile】Die Vorteile der halbierten Suchmethode sind weniger Vergleiche, eine schnelle Suchgeschwindigkeit und eine gute durchschnittliche Leistung. Der Nachteil besteht darin, dass die nachzuschlagende Tabelle eine geordnete Tabelle sowie Einfügung und Löschung sein muss sind schwierig. Daher eignet sich die binäre Suchmethode für geordnete Listen, die sich nicht häufig ändern, aber häufig durchsucht werden.
[Algorithmusidee] Vergleichen Sie zunächst das in der mittleren Position der Tabelle aufgezeichnete Schlüsselwort mit dem Suchschlüsselwort. Wenn die beiden gleich sind, ist die Suche erfolgreich, andernfalls verwenden Sie den Datensatz in der mittleren Position, um die Tabelle in zwei Untereinheiten zu unterteilen -Tabellen, die erste und die letzte. Wenn das aufgezeichnete Schlüsselwort in der mittleren Position größer als das Suchschlüsselwort ist, wird die vorherige Untertabelle weiter durchsucht, andernfalls wird die nächste Untertabelle weiter durchsucht.

<?php 
//正向排序的数组 
$arr=array(1,3,5,7,9,11); 
//逆向排序的数组 
$arr2=array(11,9,7,5,3,1); 
//对正向排序的数组进行二分查找 
function searchpart($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 
if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 
$end=$mid-1;//$arr[0]-$arr[1] 
}elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[3]-$arr[5] 
$start=$mid+1; 
}else{//找到了，返回待查值下标 
return $mid; 
} 
} 
} 
//对逆向排序的数组进行二分查找 
function searchpart2($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 
if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 
$start=$mid+1;//$arr[3]-$arr[5] 
}elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[0]-$arr[1] 
$end=$mid-1; 
}else{//找到了，返回待查值下标 
return $mid; 
} 
} 
} 
echo searchpart2($arr,5).&#39;<br>&#39;; 
echo searchpart2($arr2,5); 
?>

Implementierung des binären Suchalgorithmus in PHP
Kürzlich habe ich das Algorithmuswissen, das ich zuvor gelernt habe, geordnet. Obwohl der Algorithmus in der WEB-Entwicklung selten verwendet wird, erstelle ich dennoch einige nützliche Algorithmen.
Die Halbsuchmethode wird auch als binäre Suchmethode bezeichnet. Sie nutzt die Ordnungsbeziehung zwischen Elementen vollständig aus und übernimmt die Divide-and-Conquer-Strategie. Sie kann die Suchaufgabe in O(log n) abschließen schlimmster Fall.
[Grundidee]
Teilen Sie n Elemente in zwei Hälften mit ungefähr der gleichen Anzahl, vergleichen Sie a[n/2] mit dem x, das Sie finden möchten, wenn x=a[n/2], dann finden Sie x, Der Algorithmus terminiert. Wenn xa[n/2], müssen wir nur in der rechten Hälfte des Arrays a weiter nach x suchen.
Die binäre Suchmethode ist äußerst weit verbreitet und ihre Idee ist leicht zu verstehen. Der erste binäre Suchalgorithmus erschien bereits 1946, der erste völlig korrekte binäre Suchalgorithmus erschien jedoch erst 1962. Bentley schrieb in seinem Buch „Writing Correct Programs“, dass 90 % der Computerexperten nicht innerhalb von 2 Stunden einen völlig korrekten binären Suchalgorithmus schreiben können. Der Schlüssel zum Problem besteht darin, die Grenzen jedes Suchbereichs genau zu formulieren, die Beendigungsbedingungen zu bestimmen und die verschiedenen Situationen ungerader und gerader Zahlen richtig zusammenzufassen. Tatsächlich können wir nach dem Aussortieren feststellen, dass der spezifische Algorithmus sehr ist intuitiv.
Implementierung des binären Suchalgorithmus in PHP

/** 
* 二分查找算法 
* 
* @param array $arr 有序数组 
* @param int $val 查找的数值 
* @return int 查找值存在返回数组下标,不存在返回-1 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);//获得有序数组长度 
$low = 0; 
$high = $l -1; 
while($low <= $high) 
{ 
$middle = floor(($low + $high) / 2); 
if($arr[$middle] == $val) 
{ 
return $middle; 
} 
elseif($arr[$middle] > $val) 
{ 
$high = $middle - 1; 
} 
else 
{ 
$low = $middle + 1; 
} 
} 
return -1; 
} 
//示例 
$arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56,67,89,99); 
echo binary_search($arr,57);

Weitere Informationen zum Teilen von Code mit PHP zur Implementierung des binären Suchalgorithmus finden Sie auf der chinesischen PHP-Website!