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.

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.

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)