Au programme de ce chapitre
- I. La recherche séquentielle et la recherche dichotomique
- II. Le tri par sélection
- III. Le tri par insertion
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition La recherche séquentielle parcourt un tableau élément par élément : elle fonctionne sur n'importe quel tableau, mais dans le pire des cas examine les n éléments, d'où une complexité en O(n). Si le tableau est trié, la recherche dichotomique compare la cible à l'élément du milieu, élimine la moitié du tableau à chaque comparaison, et atteint une complexité en O(log2 n), beaucoup plus rapide pour un grand tableau.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
🔒 Infographie récapitulative du chapitreIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
🔒 Infographie récapitulative du chapitreIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Code testé avec
python3 sur le tableau trié t = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72], à la recherche de 23 :
>>> def recherche_dichotomique(t, cible):
... gauche, droite = 0, len(t) - 1
... while gauche <= droite:
... milieu = (gauche + droite) // 2
... if t[milieu] == cible:
... return milieu
... elif t[milieu] < cible:
... gauche = milieu + 1
... else:
... droite = milieu - 1
... return -1
>>> recherche_dichotomique(t, 23)
5
>>> recherche_dichotomique(t, 100)
-1Les erreurs fréquentes à éviter
Piège. La dichotomie ne marche que sur un tableau TRIÉ ; sinon, utilise la recherche séquentielle.
L'astuce du prof
Astuce. Dichotomie : couper en deux à chaque étape → très rapide sur grand tableau trié.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Quand peut-on utiliser la recherche dichotomique ?
Voir la correction
Quand le tableau est trié : on coupe en deux à chaque étape.
Exercice 2
Qu'est-ce qu'un tri par sélection ?
Voir la correction
On cherche le plus petit élément et on le place en premier, puis on recommence.