Recherche Dichotomique
Chercher un mot dans un dictionnaire de 100 000 mots... En lisant tout depuis le debut ? Ou en ouvrant au milieu et en divisant par deux a chaque essai ? La seconde methode ne prend que 17 etapes maximum !
50 min Niveau 3/5 +30 XP
Objectifs
- Implementer la recherche lineaire
- Comprendre et implementer la recherche dichotomique
- Comparer les complexites O(n) vs O(log n)
Erreurs courantes
- !Oublier que la dichotomie necessite un tableau trie
- !Erreur dans le calcul du milieu (depassement)
- !Mauvaise condition d'arret de la boucle
Cours
Principe : parcourir le tableau element par element jusqu'a trouver la valeur cherchee.
Complexite
Meilleur
O(1)
Moyen
O(n)
Pire
O(n)
Avantages
- + Simple a implementer
- + Fonctionne sur tout tableau (trie ou non)
Inconvenients
- - Lent pour les grands tableaux
- - Parcourt potentiellement tout le tableau
def recherche_lineaire(tab, valeur):
"""
Recherche valeur dans tab.
Retourne l'indice si trouve, -1 sinon.
"""
for i in range(len(tab)):
if tab[i] == valeur:
return i
return -1
# Tests
tableau = [3, 1, 4, 1, 5, 9, 2, 6]
print(f"Recherche de 5 : indice {recherche_lineaire(tableau, 5)}") # 4
print(f"Recherche de 7 : indice {recherche_lineaire(tableau, 7)}") # -1Quiz Recherche
5 questions pour tester tes connaissances
Point cle
Pour 1 million d'elements : la recherche lineaire fait 1 million d'operations, la dichotomie seulement 20 !
