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 de retour est initialisé comme

Faux et changera en Vrai lorsque la valeur souhaitée est trouvée.

Voir l'implémentation Python ci-dessous à titre d'exemple:

def linearSearch (mylist, élément):

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.

En rapport: Qu'est-ce que la notation Big-O ?

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.

En rapport: Qu'est-ce que la récursivité et comment l'utilisez-vous ?

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, élément):

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 second, 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.

Comment utiliser le tri par sélection

Le tri par sélection est un peu difficile à comprendre pour les débutants, mais ce n'est pas trop difficile une fois que vous avez compris le swing.

Lire la suite

A propos de l'auteur