La mise en œuvre d’une recherche peut sembler complexe, mais elle n’est certainement pas insurmontable.
Dans la vie de tous les jours, nous ne suivons généralement pas de modèle préétabli lors de nos recherches. Nous nous rendons simplement là où nous pensons que l’objet de notre recherche pourrait se trouver. Cette approche instinctive prévaut dans la plupart des situations.
Mais est-ce que cette même approche fonctionne efficacement dans le monde de la programmation ?
La réponse est non! Pour localiser des éléments au sein de programmes, il est nécessaire de suivre des schémas précis. Cet article explore plusieurs algorithmes qui utilisent différentes techniques pour effectuer ces recherches.
De nombreux algorithmes de recherche sont disponibles dans le domaine de la programmation. Nous allons nous concentrer sur les algorithmes les plus fondamentaux et les plus largement utilisés. Une fois que vous aurez maîtrisé ces algorithmes clés, l’apprentissage des autres deviendra beaucoup plus aisé.
Dans le contexte de cet article, la recherche fait référence à l’action de localiser un élément spécifique dans un tableau.
Examinons ces algorithmes plus en détail.
Recherche Linéaire
Comme son nom l’indique, l’algorithme de recherche linéaire parcourt le tableau de manière séquentielle, en examinant chaque élément un par un. Il commence au début du tableau et continue jusqu’à ce qu’il trouve l’élément recherché ou qu’il atteigne la fin. L’exécution du programme est interrompue dès que l’élément est trouvé.
Pour faciliter une meilleure compréhension de cet algorithme, nous allons l’illustrer avec quelques exemples visuels.
En analysant attentivement le processus de recherche, il est clair que, dans le pire des cas, le temps nécessaire à l’exécution du programme est de l’ordre de O(n). Il est essentiel d’évaluer la complexité temporelle dans le pire des cas lors de l’analyse des algorithmes. Par conséquent, la complexité temporelle de cet algorithme est de O(n).
Voyons maintenant comment implémenter l’algorithme de recherche linéaire.
Mise en œuvre de la recherche linéaire
Maintenant que vous avez une bonne idée de ce qu’est l’algorithme de recherche linéaire, il est temps de passer à la pratique avec du code. Examinons d’abord les étapes nécessaires pour sa mise en œuvre, puis essayez de le coder vous-même. Si vous rencontrez des difficultés, ne vous inquiétez pas, je vous fournirai le code par la suite.
Voici les étapes à suivre pour implémenter l’algorithme de recherche linéaire :
- Créez un tableau contenant plusieurs éléments (vos nombres préférés, par exemple).
- Définissez une fonction nommée `rechercher_element` qui prendra trois arguments : le tableau, sa longueur et l’élément que vous souhaitez localiser.
- La fonction `rechercher_element(arr, n, element)` devra effectuer les opérations suivantes :
- Parcourir tous les éléments du tableau.
- Vérifier si l’élément actuel correspond à l’élément que vous recherchez.
- Si c’est le cas, la fonction doit renvoyer la valeur `Vrai`.
- Si la boucle se termine sans que l’élément soit trouvé, cela signifie qu’il n’est pas présent dans le tableau. La fonction doit donc renvoyer `Faux`.
- Parcourir tous les éléments du tableau.
- En fonction de la valeur retournée par la fonction `rechercher_element`, affichez un message approprié.
En suivant ces étapes, écrivez maintenant le code pour mettre en œuvre l’algorithme de recherche linéaire.
Avez-vous terminé ? J’espère que oui. Si c’est le cas, comparez votre code avec celui qui suit.
Si vous n’avez pas encore terminé, ne vous inquiétez pas. Examinez le code ci-dessous et vous verrez comment nous avons procédé. Vous comprendrez facilement le principe.
## fonction de recherche
def rechercher_element(arr, n, element):
## parcours du tableau
for i in range(n):
## vérification de la correspondance avec l'élément recherché
if arr[i] == element:
## retour de Vrai si correspondance
return True
## l'élément n'a pas été trouvé, l'exécution arrive ici
return False
if __name__ == '__main__':
## initialisation du tableau, de la longueur et de l'élément à rechercher
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
element_a_rechercher = 6
# element_a_rechercher = 11
if rechercher_element(arr, n, element_a_rechercher):
print(element_a_rechercher, "est trouvé")
else:
print(element_a_rechercher, "n'est pas trouvé")
Commencez par exécuter le programme avec un élément qui est présent dans le tableau. Puis, exécutez-le à nouveau avec un élément qui n’y est pas.
La complexité temporelle de l’algorithme de recherche linéaire est O(n).
Serait-il possible de réduire cette complexité avec une approche différente ?
Oui, c’est possible. Explorons cette option.
Recherche Binaire
L’algorithme de recherche binaire procède en vérifiant systématiquement l’élément situé au milieu du tableau. Cet algorithme est applicable uniquement aux tableaux triés.
L’algorithme parcourt le tableau, compare l’élément du milieu avec l’élément recherché et arrête l’exécution si une correspondance est trouvée. Si l’élément du milieu est inférieur à l’élément recherché, l’algorithme exclut la partie gauche du tableau de la recherche. Inversement, si l’élément du milieu est supérieur, il exclut la partie droite.
A chaque itération, l’algorithme de recherche binaire réduit de moitié la zone de recherche. Par conséquent, il nécessite moins de vérifications par rapport à l’algorithme de recherche linéaire.
Des illustrations peuvent aider à mieux comprendre l’algorithme de recherche binaire. Examinons-les attentivement.
La complexité temporelle de l’algorithme de recherche binaire est de O(log n). À chaque itération, la longueur de la zone de recherche est divisée par deux, ce qui signifie une réduction exponentielle.
Mise en œuvre de la recherche binaire
Avant de passer au code, examinons les étapes à suivre pour mettre en œuvre l’algorithme de recherche binaire. Voici ces étapes :
- Créez un tableau contenant plusieurs éléments triés (vos nombres préférés, par exemple).
- Définissez une fonction nommée `rechercher_element` qui prendra trois arguments : le tableau trié, sa longueur et l’élément que vous souhaitez localiser.
- La fonction `rechercher_element(tableau_trié, n, element)` devra effectuer les opérations suivantes :
- Initialisez la variable `i` pour le parcours du tableau.
- Initialisez deux variables, `debut` et `fin`, pour marquer le début et la fin de la zone de recherche.
- Tant que `i` est inférieur à la longueur du tableau, répétez les étapes suivantes :
- Calculez l’index du milieu de la zone de recherche avec la formule : `(debut + fin) // 2`.
- Vérifiez si l’élément à l’index du milieu est égal à l’élément recherché.
- Si c’est le cas, la fonction doit retourner `Vrai`.
- Sinon, si l’élément à l’index du milieu est inférieur à l’élément recherché, définissez la nouvelle valeur de `debut` à `milieu + 1`.
- Sinon, si l’élément à l’index du milieu est supérieur à l’élément recherché, définissez la nouvelle valeur de `fin` à `milieu – 1`.
- Incrémentez l’indice du tableau `i`.
- Si la boucle se termine sans que l’élément soit trouvé, cela signifie qu’il n’est pas présent dans le tableau. La fonction doit alors renvoyer `Faux`.
- En fonction de la valeur retournée par la fonction `rechercher_element`, affichez un message approprié.
Essayez d’écrire le code vous-même en vous inspirant de l’implémentation de l’algorithme de recherche linéaire.
…
Avez-vous obtenu le code ?
Si oui, comparez-le avec celui qui suit. Si non, ne vous inquiétez pas et analysez l’implémentation dans le code ci-dessous.
## fonction de recherche
def rechercher_element(tableau_trié, n, element):
## index du tableau pour le parcours
i = 0
## variables pour suivre la zone de recherche
## initialisation avec les indices de début et de fin
debut = 0
fin = n - 1
## parcours du tableau
while i < n:
## obtention de l'index de l'élément du milieu
milieu = (debut + fin) // 2
## vérification de la correspondance de l'élément du milieu avec l'élément recherché
if tableau_trié[milieu] == element:
## retour de Vrai car l'élément est dans le tableau
return True
elif tableau_trié[milieu] < element:
## déplacement de l'indice de début de la zone de recherche vers la droite
debut = milieu + 1
else:
## déplacement de l'indice de fin de la zone de recherche vers la gauche
fin = milieu - 1
i += 1
return False
if __name__ == '__main__':
## initialisation du tableau, de la longueur et de l'élément à rechercher
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
element_a_rechercher = 9
# element_a_rechercher = 11
if rechercher_element(arr, n, element_a_rechercher):
print(element_a_rechercher, "est trouvé")
else:
print(element_a_rechercher, "n'est pas trouvé")
Testez ce code en utilisant différents cas de figure, avec des éléments présents et absents du tableau.
Conclusion
L’algorithme de recherche binaire est bien plus performant que l’algorithme de recherche linéaire. Cependant, il est crucial de trier le tableau au préalable, ce qui n’est pas requis pour la recherche linéaire. Le processus de tri a un coût en temps d’exécution, mais l’utilisation d’algorithmes de tri efficaces permet de combiner la recherche binaire avec le tri de manière optimale.
Vous disposez maintenant de solides bases concernant les algorithmes de recherche les plus utilisés en Python.
Dans un prochain temps, vous pourriez explorer les outils de recherche auto-hébergés les plus populaires.
Bon codage ! 🙂 🧑💻