Algorithmique : recherche (linéaire, dichotomique)

Introduction

L'algorithmique est au cœur de l'informatique et permet de résoudre des problèmes de manière efficace. Dans ce chapitre, nous allons explorer deux méthodes de recherche fondamentales : la recherche linéaire et la recherche dichotomique. Comprendre ces algorithmes est essentiel pour optimiser la recherche d'informations dans un ensemble de données, un enjeu crucial dans le monde numérique d'aujourd'hui. Les algorithmes de recherche sont largement utilisés dans des applications variées, allant des bases de données aux moteurs de recherche, en passant par les systèmes d'exploitation. L'efficacité d'un algorithme de recherche peut avoir un impact significatif sur la performance d'une application, rendant cette connaissance indispensable pour tout informaticien en herbe.

1. La recherche linéaire

La recherche linéaire est la méthode la plus simple pour trouver un élément dans une liste. Elle consiste à parcourir chaque élément de la liste jusqu'à ce que l'élément recherché soit trouvé ou que la liste soit entièrement examinée.

1.1 Principe de la recherche linéaire

• Complexité : O(n), où n est le nombre d'éléments dans la liste. Cela signifie que le temps de recherche augmente linéairement avec la taille de la liste. Par exemple, si une liste contient 100 éléments, dans le pire des cas, il peut être nécessaire de faire jusqu'à 100 comparaisons pour trouver un élément. Cette complexité est particulièrement problématique pour les très grandes listes, car elle peut entraîner des temps de réponse inacceptables dans des applications en temps réel.

1.2 Étapes de la recherche linéaire

1. Commencer par le premier élément de la liste.
2. Comparer l'élément courant avec l'élément recherché.
3. Si l'élément est trouvé, retourner sa position.
4. Si l'élément n'est pas trouvé, passer à l'élément suivant.
5. Répéter jusqu'à la fin de la liste.

1.3 Exemple concret

Imaginons que vous ayez une liste de 10 numéros : [3, 7, 2, 9, 5, 1, 4, 6, 8, 0]. Si vous cherchez le numéro 5, la recherche linéaire va examiner chaque élément de la liste dans l'ordre jusqu'à ce qu'elle trouve 5, ce qui prendra en moyenne 5 comparaisons (dans le pire des cas, 10 comparaisons).

Liste de nombres	Comparaisons nécessaires
-------------------	--------------------------
[3, 7, 2, 9, 5, 1, 4, 6, 8, 0]	5 (pour trouver 5)

1.4 Mini-exercice

Exercice : Vous avez la liste suivante : [12, 45, 23, 67, 34, 89, 10]. Trouvez la position du nombre 34.

Correction :
1. 12 (pas 34)
2. 45 (pas 34)
3. 23 (pas 34)
4. 67 (pas 34)
5. 34 (trouvé à la position 4)

1.5 Avantages et inconvénients

• Avantages :

- Simple à mettre en œuvre.
- Aucune condition préalable (la liste n'a pas besoin d'être triée).

• Inconvénients :