Qu'est-ce que la recherche binaire dans une liste ordonnée ?

Demi-recherche dans la liste ordonnée : prenez la valeur médiane comme objet de comparaison. Si la valeur donnée et la clé de la valeur médiane sont égales, la recherche est réussie si la valeur donnée est inférieure à la clé de ; l'enregistrement du milieu, puis dans La recherche se poursuit dans la moitié gauche de l'enregistrement du milieu.

L'environnement d'exploitation de cet article : système Windows 7, ordinateur Dell G3.

Concept de demi-recherche :

Demi-recherche, également connue sous le nom de recherche binaire.

Le principe est que les enregistrements de la table linéaire doivent être dans l'ordre des clés (de petit à grand ou de grand à petit) et que la table linéaire doit être stockée séquentiellement.

L'idée de base de la demi-recherche est la suivante : Dans une liste ordonnée, la valeur du milieu est prise comme objet de comparaison si la valeur donnée et la clé de la valeur du milieu sont égales. , la recherche réussit ; si si la valeur donnée est inférieure à la clé de l'enregistrement intermédiaire, la recherche se poursuivra dans la moitié gauche de l'enregistrement intermédiaire ; si la valeur donnée est supérieure à la clé de l'enregistrement intermédiaire, la recherche continuera dans la moitié droite du disque du milieu. Répétez le processus ci-dessus jusqu'à ce que la recherche réussisse ou qu'il n'y ait aucun enregistrement dans toutes les zones et que la recherche échoue.

Implémentation de l'algorithme :

public int Binary_Search(int[] a, int n, int key) {
int low = 1, high = n, mid;
while(low <= high) {
mid = (int)((low + high) / 2);
if(key < a[mid]) {
high = mid - 1;
}
else if(key > a[mid]) {
low = mid + 1;
}
else return mid;
}
return 0;
}

Habituellement, trois pointeurs low, high, mid sont utilisés. Représentent respectivement l'indice de valeur le plus à gauche de la zone de recherche, l'indice de valeur le plus à droite de la zone de recherche et l'indice de valeur de comparaison actuel.

Analyse de la complexité temporelle :

La moitié de la recherche équivaut en fait à diviser la table de recherche ordonnée statique en deux sous-arbres, c'est-à-dire que seule la moitié des données doit être trouvée pendant la recherche. C’est tout, ce qui signifie que la charge de travail est réduite de moitié pour gagner en efficacité.

Recommandations vidéo associées : Programmation PHP de l'entrée à la maîtrise

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!