Français
Français
La recherche d'un demi-pli (également connu sous le nom de recherche binaire) est un algorithme efficace pour trouver des éléments cibles dans un tableau ordonné. L'algorithme rétrécit progressivement la plage de recherche en divisant en continu le tableau en deux moitiés, en comparant la taille de la valeur cible avec l'élément intermédiaire, jusqu'à ce que l'élément cible soit trouvé ou qu'il soit déterminé qu'il n'existe pas.
Les étapes de base de la recherche de moitié pliante comprennent:
1. Réglez la position de début du tableau à gauche et la position d'extrémité à droite .
2. Calculez la position intermédiaire Mid = (gauche + droite) / 2 .
3. Comparez la valeur cible avec l'élément de position intermédiaire:
4. Répétez les étapes ci-dessus jusqu'à ce que la valeur cible soit trouvée ou à gauche> à droite , et la recherche échoue.
Le code PHP suivant implémente l'algorithme de recherche à moitié d'abondance:
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = intval(($left + $right) / 2);
if ($arr[$mid] == $target) {
return $mid; // Renvoie l'index de la valeur cible dans le tableau
}
if ($arr[$mid] < $target) {
$left = $mid + 1; // Continuez à rechercher sur la moitié droite
} else {
$right = $mid - 1; // Continuez à rechercher sur la moitié gauche
}
}
return -1; // La valeur cible n'existe pas
}
<p>$arr = [1, 3, 5, 7, 9, 11, 15];<br>
$target = 7;<br>
$index = binarySearch($arr, $target);<br>
if ($index != -1) {<br>
echo "Valeur cible $target La position dans le tableau est $index";<br>
} else {<br>
echo "Valeur cible $target N'existe pas dans le tableau";<br>
}<br>
Le code ci-dessus définit la fonction BinarySearch , qui reçoit un tableau ordonné et une valeur cible comme paramètres, renvoie l'indice de position de la valeur cible dans le tableau et renvoie -1 s'il n'existe pas.
La complexité temporelle de la recherche à moitié d'abondance est O (Logn) , où n est la longueur du tableau. Étant donné que chaque recherche réduit la plage de moitié, les performances sont bien meilleures que les recherches linéaires, qui conviennent aux éléments de positionnement rapides dans de grands tableaux ordonnés.
Le pliage à moitié de la recherche raccourcit considérablement le temps de recherche, en particulier lorsque le volume de données est important, il peut rapidement localiser les éléments cibles, en évitant l'inefficacité de traverser l'ensemble du réseau.
Dans les scénarios d'application qui nécessitent des recherches fréquentes, l'utilisation de recherches en demi-finale peut réduire les frais généraux globaux du programme, réduire la consommation de ressources, améliorer la vitesse de réponse et l'expérience utilisateur.
Cet article présente les principes, le code d'implémentation et l'analyse des performances de l'algorithme de recherche à moitié de recherche PHP. La maîtrise de la recherche binaire est particulièrement importante pour développer des applications PHP efficaces, ce qui peut améliorer efficacement la vitesse de recherche et optimiser les performances du programme. Il est recommandé que les développeurs comprennent et utilisent de manière flexible cet algorithme.
