Explication des algorithmes de recherche linéaire et binaire
La possibilité de rechercher certaines données est un aspect important de l'informatique. Les algorithmes de recherche sont utilisés pour rechercher un élément particulier dans un ensemble de données.
Les algorithmes renvoient un résultat booléen (vrai ou faux) à une requête de recherche. Ils peuvent également être modifiés pour donner la position relative de la valeur trouvée.
Pour cet article, les algorithmes se concentreront sur la détermination de l'existence d'une valeur.
Algorithmes de recherche linéaire
La recherche linéaire est également appelée recherche séquentielle. Dans ce type de recherche, chaque valeur d'une liste est visitée une par une de manière ordonnée tout en vérifiant si la valeur souhaitée existe.
L'algorithme vérifie valeur par valeur jusqu'à ce qu'il trouve la valeur que vous recherchez ou qu'il manque de valeurs à rechercher. Lorsqu'il n'y a plus de valeurs à rechercher, cela signifie que votre requête de recherche n'existe pas dans la liste.
Un algorithme de recherche séquentiel prend une liste de valeurs et l'élément souhaité dans la liste comme paramètres. Le résultat renvoyé est initialisé comme False et passe à True lorsque la valeur souhaitée est trouvée.
Voir l'implémentation Python ci-dessous à titre d'exemple :
def linearSearch(mylist, item):
trouvé = Faux
indice = 0
while index < len(mylist) et introuvable :
si maliste[index] == élément :
trouvé = vrai
autre:
indice = indice+1
retour trouvé
Analyse d'algorithmes
Le meilleur des cas se produit lorsque l'élément souhaité est le premier de la liste. Le pire des cas se produit lorsque l'élément souhaité est le dernier de la liste (le nième élément). Par conséquent, la complexité temporelle pour la recherche linéaire est O(n).
Le scénario de cas moyen dans l'algorithme ci-dessus est n/2.
Recherche linéaire modifiée
Il est important de savoir que l'algorithme utilisé suppose qu'une liste aléatoire d'éléments lui est fournie. C'est-à-dire que les éléments de la liste ne sont pas dans un ordre particulier.
Supposons que les éléments soient dans un ordre particulier, disons du plus petit au plus grand. Il serait possible d'obtenir un certain avantage dans le calcul.
Prenons l'exemple de la recherche de 19 dans la liste donnée : [2, 5, 6, 11, 15, 18, 23, 27, 34]. Après avoir atteint 23, il deviendrait clair que l'élément recherché n'existe pas dans la liste. Par conséquent, il ne serait plus important de continuer à rechercher le reste des éléments de la liste.
Algorithmes de recherche binaire
Vous avez vu comment une liste ordonnée peut réduire le calcul nécessaire. L'algorithme de recherche binaire profite encore plus de cette efficacité qu'une liste ordonnée introduit.
L'algorithme commence par prendre une valeur médiane d'une liste ordonnée et vérifier si c'est la valeur souhaitée. Si ce n'est pas le cas, la valeur est vérifiée si elle est inférieure ou supérieure à la valeur souhaitée.
Si c'est moins, alors il n'est pas nécessaire de vérifier la moitié inférieure de la liste. Sinon, s'il est supérieur, il passe à la moitié supérieure de la liste.
Quelle que soit la sous-liste (gauche ou droite) choisie, la valeur médiane sera à nouveau déterminée. La valeur est à nouveau vérifiée si c'est la valeur requise. Si ce n'est pas le cas, il est vérifié s'il est inférieur ou supérieur à la valeur demandée.
Ce processus est répété jusqu'à ce qu'une valeur soit trouvée si elle existe.
L'implémentation Python ci-dessous concerne l'algorithme de recherche binaire.
def binarySearch(mylist, item):
faible = 0
haut = len(mylist) – 1
trouvé = Faux
tant que faible <= élevé et introuvable :
moyen = (bas + haut) // 2
if mylist[mid] == élément :
trouvé = vrai
élément elif < mylist[mid] :
haut = moyen – 1
autre:
bas = moyen + 1
retour trouvé
Analyse d'algorithmes
Le meilleur des cas se produit lorsque l'élément souhaité s'avère être l'élément du milieu. Le pire des cas n'est cependant pas aussi simple. Suivez l'analyse ci-dessous :
Après la première comparaison, n/2 éléments seront laissés. Après le deuxième, n/4 éléments seront laissés. Après le troisième, n/8.
Notez que le nombre d'éléments continue de diminuer de moitié jusqu'à ce qu'ils atteignent n/2i où i est le nombre de comparaisons. Après tout le fractionnement, nous nous retrouvons avec seulement 1 article.
Cela implique:
n/2i=1
Par conséquent, la recherche binaire est O(log n).
Passer au tri
Dans la recherche binaire, nous avons considéré un cas où le tableau donné était déjà ordonné. Mais supposons que vous ayez un ensemble de données non ordonné et que vous vouliez effectuer une recherche binaire dessus. Qu'est-ce que tu ferais?
La réponse est simple : triez-le. Il existe un certain nombre de techniques de tri en informatique qui ont fait l'objet de nombreuses recherches. L'une de ces techniques que vous pouvez commencer à étudier est l'algorithme de tri par sélection, tandis que nous avons également de nombreux guides liés à d'autres domaines.