Utiliser PHP pour implémenter le partage de code d'algorithme de recherche binaire

La première méthode :
[Exigences de recherche binaire] : 1. Une structure de stockage séquentielle doit être utilisée 2. Elle doit être organisée dans l'ordre en fonction de la taille des mots-clés.
【Avantages et inconvénients】Les avantages de la méthode de recherche divisée par deux sont moins de comparaisons, une vitesse de recherche rapide et de bonnes performances moyennes ; son inconvénient est que la table à rechercher doit être une table ordonnée, ainsi que l'insertion et la suppression ; sont difficiles. Par conséquent, la méthode de recherche binaire convient aux listes ordonnées qui ne changent pas fréquemment mais sont fréquemment recherchées.
[Idée d'algorithme] Tout d'abord, comparez le mot-clé enregistré en position médiane du tableau avec le mot-clé de recherche. Si les deux sont égaux, la recherche est réussie, sinon, utilisez l'enregistrement de position médiane pour diviser le tableau en deux sous ; -tables, le premier et le dernier. Si l'enregistrement de la position médiane Si le mot-clé enregistré est supérieur au mot-clé de recherche, alors la sous-table précédente sera recherchée plus loin, sinon la sous-table suivante sera recherchée plus loin.

<?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); 
?>

Implémentation d'un algorithme de recherche binaire en PHP
Récemment, j'ai trié les connaissances en algorithme que j'ai apprises auparavant. Bien que l'algorithme soit rarement utilisé dans le développement WEB, je crée toujours des algorithmes utiles.
La méthode de demi-recherche est également appelée méthode de recherche binaire. Elle utilise pleinement la relation d'ordre entre les éléments et adopte la stratégie diviser pour régner. Elle peut effectuer la tâche de recherche en O(log n) dans le. le pire des cas.
[Idée de base]
Divisez n éléments en deux moitiés avec à peu près le même nombre, comparez a[n/2] avec le x que vous voulez trouver, si x=a[n/2] alors trouvez x , l'algorithme se termine. Si xa[n/2], alors il suffit de continuer à chercher x dans la moitié droite du tableau a.
La méthode de recherche binaire est extrêmement largement utilisée et son idée est facile à comprendre. Le premier algorithme de recherche binaire est apparu dès 1946, mais le premier algorithme de recherche binaire complètement correct n'est apparu qu'en 1962. Bentley a écrit dans son livre "Writing Correct Programs" que 90 % des experts en informatique ne peuvent pas écrire un algorithme de recherche binaire complètement correct en 2 heures. La clé du problème est de formuler avec précision les limites de chaque plage de recherche et de déterminer les conditions de terminaison, et de résumer correctement les différentes situations de nombres impairs et pairs. En fait, après l'avoir trié, nous pouvons constater que son algorithme spécifique est très. intuitif.
Implémentation de l'algorithme de recherche binaire en 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);

Pour plus de partage de code utilisant PHP pour implémenter l'algorithme de recherche binaire, veuillez faire attention au site Web chinois de PHP !