Introduction

La recherche de données stockées dans différentes structures de données est une partie cruciale d’à peu près chaque application unique.

Il existe de nombreux algorithmes différents disponibles à utiliser lors de la recherche, et chacun a différentes implémentations et s’appuie sur différentes structures de données pour faire le travail.

Etre capable de choisir un algorithme spécifique pour une tâche donnée est une compétence clé pour les développeurs et peut faire la différence entre une application rapide, fiable et stable et une application qui s’effrite à partir d’une simple requête.

• Opérateurs d’appartenance
• Recherche linéaire
• Recherche binaire
• Recherche par saut
• Recherche de Fibonacci
• Recherche exponentielle
• Recherche par interpolation

.

Opérateurs d’appartenance

Les algorithmes se développent et s’optimisent au fil du temps en raison d’une évolution constante et de la nécessité de trouver les solutions les plus efficaces pour les problèmes sous-jacents dans différents domaines.

L’un des problèmes les plus courants dans le domaine de l’informatique est de rechercher dans une collection et de déterminer si un objet donné est présent ou non dans la collection.

Presque chaque langage de programmation a sa propre implémentation d’un algorithme de recherche de base, généralement sous la forme d’une fonction qui renvoie une valeur Boolean de True ou False lorsqu’un objet est trouvé dans une collection d’objets donnée.

En Python, la façon la plus simple de rechercher un objet est d’utiliser les opérateurs d’appartenance – nommés ainsi parce qu’ils nous permettent de déterminer si un objet donné est un membre dans une collection.

Ces opérateurs peuvent être utilisés avec n’importe quelle structure de données itérable en Python, y compris les chaînes, les listes et les tuples.

• in – Renvoie True si l’élément donné fait partie de la structure.
• not in – Renvoie True si l’élément donné ne fait pas partie de la structure.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Les opérateurs d’appartenance suffisent lorsque tout ce que nous avons besoin de faire est de trouver si une sous-chaîne existe dans une chaîne donnée, ou de déterminer si deux chaînes, listes ou tuples se croisent en termes d’objets qu’ils contiennent.

Dans la plupart des cas, nous avons besoin de la position de l’élément dans la séquence, en plus de déterminer s’il existe ou non ; les opérateurs d’appartenance ne répondent pas à cette exigence.

Il existe de nombreux algorithmes de recherche qui ne dépendent pas des opérateurs intégrés et qui peuvent être utilisés pour rechercher des valeurs plus rapidement et/ou plus efficacement. En outre, ils peuvent donner plus d’informations, comme la position de l’élément dans la collection, plutôt que de pouvoir simplement déterminer son existence.

Recherche linéaire

La recherche linéaire est l’un des algorithmes de recherche les plus simples, et le plus facile à comprendre. Nous pouvons le considérer comme une version accélérée de notre propre mise en œuvre de l’opérateur in de Python.

L’algorithme consiste à itérer sur un tableau et à renvoyer l’indice de la première occurrence d’un élément une fois qu’il est trouvé :

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Donc si nous utilisons la fonction pour calculer :

>>> print(LinearSearch(, 2))

Lorsque nous exécutons le code, nous sommes accueillis par :

1

C’est l’indice de la première occurrence de l’élément que nous recherchons – en gardant à l’esprit que les indices Python sont basés sur 0.

La complexité temporelle de la recherche linéaire est O(n), ce qui signifie que le temps d’exécution augmente avec le nombre d’éléments de notre liste d’entrée lys.

La recherche linéaire n’est pas souvent utilisée dans la pratique, car la même efficacité peut être obtenue en utilisant des méthodes intégrées ou des opérateurs existants, et elle n’est pas aussi rapide ou efficace que d’autres algorithmes de recherche.

La recherche linéaire convient bien lorsque nous devons trouver la première occurrence d’un élément dans une collection non triée, car contrairement à la plupart des autres algorithmes de recherche, elle ne nécessite pas qu’une collection soit triée avant de commencer la recherche.

Recherche binaire

La recherche binaire suit une méthodologie de type diviser pour régner. Elle est plus rapide que la recherche linéaire mais nécessite que le tableau soit trié avant l’exécution de l’algorithme.

En supposant que nous recherchons une valeur val dans un tableau trié, l’algorithme compare val à la valeur de l’élément central du tableau, que nous appellerons mid.

• Si mid est l’élément recherché (meilleur cas), nous retournons son indice.
• Si ce n’est pas le cas, nous identifions de quel côté de mid val est plus susceptible de se trouver en fonction du fait que val est plus petit ou plus grand que mid, et nous rejetons l’autre côté du tableau.
• Nous suivons ensuite de manière récursive ou itérative les mêmes étapes, en choisissant une nouvelle valeur pour mid, en la comparant à val et en écartant la moitié des correspondances possibles à chaque itération de l’algorithme.

L’algorithme de recherche binaire peut être écrit de manière récursive ou itérative. La récursion est généralement plus lente en Python car elle nécessite l’allocation de nouveaux cadres de pile.

Puisqu’un bon algorithme de recherche doit être aussi rapide et précis que possible, considérons l’implémentation itérative de la recherche binaire :

Si nous utilisons la fonction pour calculer :

>>> BinarySearch(, 20)

Nous obtenons le résultat :

1

Qui est l’indice de la valeur que nous recherchons.

L’action que l’algorithme effectue ensuite à chaque itération est l’une de plusieurs possibilités :

• Retourner l’indice de l’élément courant
• Recherche dans la moitié gauche du tableau
• Recherche dans la moitié droite du tableau

Nous ne pouvons choisir qu’une seule possibilité par itération, et notre pool de correspondances possibles est divisé par deux à chaque itération. Cela rend la complexité temporelle de la recherche binaire O(log n).

Un inconvénient de la recherche binaire est que s’il y a plusieurs occurrences d’un élément dans le tableau, elle ne retourne pas l’indice du premier élément, mais plutôt l’indice de l’élément le plus proche du milieu :

>>> print(BinarySearch(, 4))

En exécutant ce morceau de code, on obtiendra l’indice de l’élément du milieu :

1

Pour comparaison, exécuter une recherche linéaire sur le même tableau renverrait :

0

C’est-à-dire l’indice du premier élément. Cependant, nous ne pouvons pas dire catégoriquement que la recherche binaire ne fonctionne pas si un tableau contient deux fois le même élément – elle peut fonctionner comme la recherche linéaire et retourner la première occurrence de l’élément dans certains cas.

Si nous effectuons une recherche binaire sur le tableau par exemple, et que nous recherchons 4, nous obtiendrons 3 comme résultat.

La recherche binaire est assez couramment utilisée dans la pratique car elle est efficace et rapide par rapport à la recherche linéaire. Cependant, elle présente quelques inconvénients, comme sa dépendance à l’opérateur //. Il existe de nombreux autres algorithmes de recherche par division et conquête qui sont dérivés de la recherche binaire, examinons-en quelques-uns ensuite.

Recherche par saut

La recherche par saut est similaire à la recherche binaire en ce sens qu’elle fonctionne sur un tableau trié, et utilise une approche similaire de division et conquête pour rechercher dans ce tableau.

Il peut être classé comme une amélioration de l’algorithme de recherche linéaire puisqu’il dépend de la recherche linéaire pour effectuer la comparaison réelle lors de la recherche d’une valeur.

Donné un tableau trié, au lieu de rechercher à travers les éléments du tableau de manière incrémentielle, nous recherchons par sauts. Ainsi, dans notre liste d’entrée lys, si nous avons une taille de saut de saut, notre algorithme considérera les éléments dans l’ordre lys, lys, lys, lys et ainsi de suite.

A chaque saut, nous stockons la valeur précédente que nous avons regardée et son index. Lorsque nous trouvons un ensemble de valeurs où lys<élément<lys, nous effectuons une recherche linéaire avec lys comme élément le plus à gauche et lys comme élément le plus à droite dans notre ensemble de recherche :

Comme il s’agit d’un algorithme complexe, considérons le calcul étape par étape de la recherche par saut avec cette entrée :

>>> print(JumpSearch(, 5))

• La recherche par saut déterminerait d’abord la taille du saut en calculant math.sqrt(len(lys)). Comme nous avons 9 éléments, la taille du saut serait √9 = 3.
• Puis, nous calculons la valeur de la variable right, qui est le minimum de la longueur du tableau moins 1, ou la valeur de left+jump, qui dans notre cas serait 0+3= 3. Puisque 3 est plus petit que 8, nous utilisons 3 comme valeur de right.
• Maintenant nous vérifions si notre élément de recherche, 5, est entre lys et lys. Comme 5 n’est pas entre 1 et 4, nous passons à autre chose.
• Puis, nous refaisons les calculs et vérifions si notre élément de recherche est entre lys et lys, où 6 est 3+saut. Puisque 5 est entre 4 et 7, nous effectuons une recherche linéaire sur les éléments entre lys et lys et retournons l’indice de notre élément comme:

4

La complexité temporelle de la recherche par saut est O(√n), où √n est la taille du saut et n est la longueur de la liste, ce qui place la recherche par saut entre la recherche linéaire et les algorithmes de recherche binaire en termes d’efficacité.

L’avantage unique le plus important de la recherche par saut par rapport à la recherche binaire est qu’elle ne repose pas sur l’opérateur de division (/).

Dans la plupart des CPU, l’utilisation de l’opérateur de division est coûteuse par rapport aux autres opérations arithmétiques de base (addition, soustraction et multiplication), parce que la mise en œuvre de l’algorithme de division est itérative.

Le coût en lui-même est très faible, mais lorsque le nombre d’éléments à rechercher est très grand, et que le nombre d’opérations de division que nous devons effectuer augmente, le coût peut s’additionner de façon incrémentielle. Par conséquent, la recherche par saut est meilleure que la recherche binaire lorsqu’il y a un grand nombre d’éléments dans un système où même une petite augmentation de la vitesse compte.

Pour rendre la recherche par saut plus rapide, nous pourrions utiliser la recherche binaire ou une autre recherche par saut interne pour rechercher dans les blocs, au lieu de compter sur la recherche linéaire beaucoup plus lente.

Recherche de Fibonacci

La recherche de Fibonacci est un autre algorithme de division et de conquête qui présente des similitudes avec la recherche binaire et la recherche par saut. Il tire son nom du fait qu’il utilise les nombres de Fibonacci pour calculer la taille du bloc ou la plage de recherche à chaque étape.

Les nombres de Fibonacci commencent par zéro et suivent le modèle 0, 1, 1, 2, 3, 5, 8, 13, 21… où chaque élément est l’addition des deux nombres qui le précèdent immédiatement.

L’algorithme fonctionne avec trois nombres de Fibonacci à la fois. Appelons les trois nombres fibM, fibM_minus_1, et fibM_minus_2 où fibM_minus_1 et fibM_minus_2 sont les deux nombres immédiatement avant fibM dans la séquence:

fibM = fibM_minus_1 + fibM_minus_2

Nous initialisons les valeurs à 0,1, et 1 ou les trois premiers nombres de la séquence de Fibonacci pour éviter d’obtenir une erreur d’index dans le cas où notre tableau de recherche lys contient un très petit nombre d’éléments.

Puis nous choisissons le plus petit nombre de la séquence de Fibonacci qui est supérieur ou égal au nombre d’éléments de notre tableau de recherche lys, comme valeur de fibM, et les deux nombres de Fibonacci immédiatement avant comme valeurs de fibM_minus_1 et fibM_minus_2. Tant qu’il reste des éléments dans le tableau et que la valeur de fibM est supérieure à un, on:

• Compare val avec la valeur du bloc dans la plage jusqu’à fibM_minus_2, et renvoie l’indice de l’élément s’il correspond.
• Si la valeur est supérieure à l’élément que nous regardons actuellement, nous déplaçons les valeurs de fibM, fibM_minus_1 et fibM_minus_2 de deux pas vers le bas dans la séquence de Fibonacci, et nous réinitialisons l’indice à l’indice de l’élément.
• Si la valeur est inférieure à l’élément que nous regardons actuellement, nous déplaçons les valeurs de fibM, fibM_minus_1 et fibM_minus_2 d’un pas vers le bas dans la séquence de Fibonacci.

Regardons l’implémentation Python de cet algorithme :

Si nous utilisons la fonction FibonacciSearch pour calculer :

>>> print(FibonacciSearch(, 6))

Regardons le processus étape par étape de cette recherche :

• Déterminer le plus petit nombre de Fibonacci supérieur ou égal à la longueur de la liste comme fibM ; dans ce cas, le plus petit nombre de Fibonacci répondant à nos exigences est 13.
• Les valeurs seraient attribuées comme:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• Puis, nous vérifions l’élément lys où 4 est le minimum de -1+5 . Puisque la valeur de lys est 5, ce qui est plus petit que la valeur que nous recherchons, nous déplaçons les nombres de Fibonacci d’un cran vers le bas dans la séquence, ce qui donne les valeurs :
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• Puis, nous vérifions l’élément lys où 7 est le minimum de 4+3. Comme la valeur de lys est 8, ce qui est supérieur à la valeur que nous recherchons, nous déplaçons les nombres de Fibonacci deux pas plus bas dans la séquence.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Nous vérifions maintenant l’élément lys où 5 est le minimum de 4+1 . La valeur de lys est 6, ce qui est la valeur que nous recherchons!

Le résultat, comme prévu est:

5

La complexité temporelle de la recherche de Fibonacci est O(log n) ; la même que la recherche binaire. Cela signifie que l’algorithme est plus rapide que la recherche linéaire et la recherche par saut dans la plupart des cas.

La recherche de Fibonacci peut être utilisée lorsque nous avons un très grand nombre d’éléments à rechercher, et que nous voulons réduire l’inefficacité associée à l’utilisation d’un algorithme qui repose sur l’opérateur de division.

Un avantage supplémentaire de l’utilisation de la recherche de Fibonacci est qu’elle peut s’adapter à des tableaux d’entrée qui sont trop grands pour être maintenus dans le cache du CPU ou dans la RAM, parce qu’elle recherche à travers les éléments dans des tailles de pas croissantes, et non dans une taille fixe.

Recherche exponentielle

La recherche exponentielle est un autre algorithme de recherche qui peut être implémenté assez simplement en Python, comparé à la recherche par saut et à la recherche de Fibonacci qui sont toutes deux un peu complexes. Elle est également connue sous les noms de recherche galopante, recherche double et recherche Struzik.

La recherche exponentielle dépend de la recherche binaire pour effectuer la comparaison finale des valeurs. L’algorithme fonctionne en :

• Déterminant la plage où l’élément que nous recherchons est susceptible de se trouver
• Utilisant la recherche binaire pour la plage afin de trouver l’indice exact de l’élément

L’implémentation Python de l’algorithme de recherche exponentielle est :

Si nous utilisons la fonction pour trouver la valeur de :

>>> print(ExponentialSearch(,3))

L’algorithme fonctionne en :

• Vérifiant si le premier élément de la liste correspond à la valeur que nous recherchons – puisque lys est 1 et que nous recherchons 3, nous mettons l’indice à 1 et nous continuons.
• Vérifier si le premier élément de la liste correspond à la valeur que nous recherchons – puisque lys vaut 1 et que nous recherchons 3, nous fixons l’indice à 1 et continuons :
  • index = 1, lysest 2, ce qui est inférieur à 3, donc l’indice est multiplié par 2 et fixé à 2.
  • index = 2, lysest 3, ce qui est égal à 3, donc l’indice est multiplié par 2 et fixé à 4.
  • index = 4, lysest 5, ce qui est supérieur à 3 ; la boucle est interrompue à ce stade.
• Il effectue ensuite une recherche binaire en tranchant la liste ; arr. En Python, cela signifie que la sous liste contiendra tous les éléments jusqu’au 4ème élément, donc nous appelons en fait :

>>> BinarySearch(, 3)

ce qui renverrait :

2

C’est l’indice de l’élément que nous recherchons à la fois dans la liste d’origine, et dans la liste tranchée que nous transmettons à l’algorithme de recherche binaire.

La recherche exponentielle s’exécute en temps O(log i), où i est l’indice de l’élément que nous recherchons. Dans son pire cas, la complexité temporelle est O(log n), lorsque le dernier élément est celui que nous recherchons (n étant la longueur du tableau).

La recherche exponentielle fonctionne mieux que la recherche binaire lorsque l’élément que nous recherchons est plus proche du début du tableau. En pratique, nous utilisons la recherche exponentielle car c’est l’un des algorithmes de recherche les plus efficaces pour les tableaux non bornés ou infinis.

Recherche par interpolation

La recherche par interpolation est un autre algorithme de type diviser pour régner, similaire à la recherche binaire. Contrairement à la recherche binaire, elle ne commence pas toujours la recherche au milieu. La recherche par interpolation calcule la position probable de l’élément que nous recherchons en utilisant la formule :

index = low + )*(high-low) / (lys-lys)]

Où les variables sont :

• lys – notre tableau d’entrée
• val – l’élément que nous recherchons
• index – l’indice probable de l’élément recherché. Il est calculé pour être une valeur plus élevée lorsque val est plus proche en valeur de l’élément à la fin du tableau (lys), et plus faible lorsque val est plus proche en valeur de l’élément au début du tableau (lys)
• low – l’indice de départ du tableau
• high – le dernier indice du tableau

L’algorithme recherche en calculant la valeur de index :

• Si une correspondance est trouvée (lorsque lys == val), l’indice est renvoyé
• Si la valeur de val est inférieure à lys, la valeur de l’indice est recalculée en utilisant la formule pour le sous-réseau gauche
• Si la valeur de val est supérieure à lys, la valeur de l’indice est recalculée en utilisant la formule pour le sous-réseau de droite

Poursuivons et implémentons la recherche par interpolation en utilisant Python :

Si nous utilisons la fonction pour calculer :

>>> print(InterpolationSearch(, 6))

Nos valeurs initiales seraient :

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Puisque lys est 6, qui est la valeur que nous recherchons, nous arrêtons l’exécution et retournons le résultat :

5

Si nous avons un grand nombre d’éléments, et que notre indice ne peut être calculé en une seule itération, nous continuons à recalculer les valeurs de l’indice après avoir ajusté les valeurs de high et low dans notre formule.

La complexité temporelle de la recherche par interpolation est O(log log n) lorsque les valeurs sont uniformément distribuées. Si les valeurs ne sont pas uniformément distribuées, la complexité temporelle dans le pire des cas est O(n), la même que la recherche linéaire.

La recherche par interpolation fonctionne mieux sur des tableaux triés et uniformément distribués. Alors que la recherche binaire commence au milieu et divise toujours en deux, la recherche par interpolation calcule la position probable de l’élément et vérifie l’index, ce qui rend plus probable la recherche de l’élément dans un plus petit nombre d’itérations.

Pourquoi utiliser Python pour la recherche ?

Python est très lisible et efficace par rapport aux anciens langages de programmation comme Java, Fortran, C, C++, etc. Un avantage clé de l’utilisation de Python pour la mise en œuvre d’algorithmes de recherche est que vous n’avez pas à vous soucier du casting ou du typage explicite.

En Python, la plupart des algorithmes de recherche que nous avons discutés fonctionneront tout aussi bien si nous recherchons une Chaîne. Gardez à l’esprit que nous devons apporter des modifications au code pour les algorithmes qui utilisent l’élément de recherche pour les calculs numériques, comme l’algorithme de recherche par interpolation.

Python est également un bon endroit pour commencer si vous voulez comparer les performances de différents algorithmes de recherche pour votre ensemble de données ; la construction d’un prototype en Python est plus facile et plus rapide car vous pouvez faire plus avec moins de lignes de code.

Pour comparer les performances de nos algorithmes de recherche implémentés par rapport à un ensemble de données, nous pouvons utiliser la bibliothèque time en Python :

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Conclusion

Il existe de nombreuses façons possibles de rechercher un élément dans une collection. Dans cet article, nous avons tenté de discuter de quelques algorithmes de recherche et de leurs implémentations en Python.

Le choix de l’algorithme à utiliser est basé sur les données que vous devez rechercher ; votre tableau d’entrée, que nous avons appelé lys dans toutes nos implémentations.

• Si vous voulez rechercher dans un tableau non trié ou trouver la première occurrence d’une variable de recherche, la meilleure option est la recherche linéaire.
• Si vous voulez rechercher dans un tableau trié, il existe de nombreuses options dont la méthode la plus simple et la plus rapide est la recherche binaire.
• Si vous avez un tableau trié que vous voulez rechercher sans utiliser l’opérateur de division, vous pouvez utiliser la recherche par saut ou la recherche Fibonacci.
• Si vous savez que l’élément que vous recherchez est susceptible d’être plus proche du début du tableau, vous pouvez utiliser la recherche exponentielle.
• Si votre tableau trié est également uniformément distribué, l’algorithme de recherche le plus rapide et le plus efficace à utiliser serait la recherche par interpolation.

Si vous n’êtes pas sûr de l’algorithme à utiliser avec un tableau trié, essayez simplement chacun d’entre eux avec la bibliothèque temporelle de Python et choisissez celui qui se comporte le mieux avec votre ensemble de données.