Listes et recherche dichotomique en Python : cours et exercices corrigés

Q: Comment écrire une recherche dichotomique en Python ?

La zone de recherche va de l'indice `g` à l'indice `d`, compris : au départ `g = 0` et `d = len(L) - 1`. Tant que `g <= d`, on calcule le milieu `m = (g + d) // 2` ; si `L[m] == x`, on renvoie `m` ; si `L[m] < x`, on continue à droite avec `g = m + 1` ; sinon, à gauche avec `d = m - 1`. Après la boucle, on renvoie `-1`. Le milieu se calcule avec `//`, car un flottant n'est pas un indice. La liste doit être triée : c'est une précondition, que la fonction ne vérifie pas. Si plusieurs éléments valent `x`, elle renvoie l'indice de l'un d'eux, pas forcément le premier.

Q: Quelle est la complexité de la recherche dichotomique ?

Sur une liste de n ≥ 1 éléments, elle fait au plus ⌊log_2 n⌋ + 1 tours : 10 pour 1000 éléments, 20 pour un million, 30 pour un milliard. Son coût est logarithmique, en O(log n). La recherche séquentielle fait au pire n tours, quand la valeur est absente ou en dernière position : son coût est linéaire, en O(n). Le prix de la dichotomie est que la liste doit être triée ; trier coûte plus qu'une recherche séquentielle, et l'on trie une fois quand on doit ensuite chercher souvent.

Q: Quel est le variant et l'invariant de la recherche dichotomique ?

Le variant est d - g + 1, le nombre de cases de la zone : c'est un entier strictement positif tant que `g <= d`, et il diminue d'au moins 1 à chaque tour, puisque le milieu examiné est retiré de la zone. d - g convient aussi, car il est positif ou nul à l'entrée de chaque tour, même s'il vaut -1 à la sortie. L'invariant est : les éléments d'indice inférieur à g sont strictement plus petits que x, ceux d'indice supérieur à d strictement plus grands. À la sortie de la boucle, g = d + 1 : aucun élément ne vaut x, et renvoyer -1 est juste.

Q: Pourquoi M = L ne copie pas une liste en Python ?

`M = L` donne deux noms à une seule liste : modifier `M[0]` modifie `L[0]`. Pour obtenir une nouvelle liste, on écrit `L[:]` ou `[x for x in L]` ; c'est une copie superficielle, qui partage les sous-listes. Une grille se crée par `[[0] * p for i in range(n)]`, jamais par `[[0] * p] * n`, qui répète n fois la même ligne. Une fonction ne modifie la liste reçue que si sa spécification le dit. Au programme marocain, `copy.deepcopy(L)` copie tous les niveaux.

Q: Comment chercher un élément dans une liste Python sans utiliser in ?

On écrit une recherche séquentielle : `for i in range(len(L))`, et `return i` dès que `L[i] == x` ; après la boucle, `return -1`. Pour un simple test d'appartenance, une boucle `while i < len(L) and L[i] != x` avance `i`, puis l'on renvoie `i < len(L)`. L'expression `x in L` fait la même recherche, au même coût, jusqu'à `len(L)` comparaisons ; quand un sujet demande d'écrire la recherche, on écrit la boucle. En France, `x in L` sur une liste n'est utilisable qu'avec la documentation du sujet.

Q: Combien coûtent les opérations sur une liste Python ?

`L[i]`, `L[i] = v`, `len(L)` et `L.pop()` ont un coût constant, et `L.append(x)` un coût constant en moyenne. Une tranche, une copie, la concaténation `+`, le test `x in L` et la comparaison `L1 == L2` coûtent un temps proportionnel au nombre d'éléments recopiés ou comparés. Écrire `L = L + [x]` dans une boucle de n tours recopie n(n - 1)/2 éléments : le coût est quadratique, alors qu'avec `L.append(x)` il est linéaire pour la boucle entière. Au programme marocain, `insert`, `remove`, `pop(i)`, `index` et `count` ont un coût linéaire.

Listes Python : création, indexation, tranches, mutabilité et alias, compréhensions, listes de listes ; algorithmes de parcours (somme, maximum, comptage), recherche séquentielle d'un élément, recherche dichotomique dans une liste triée, avec terminaison, correction et coût.

18méthodes
35exercices corrigés
3problèmes
21pièges
40figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

La recherche dichotomique cherche une valeur dans une liste triée en la comparant à l'élément du milieu, puis en ne gardant que la moitié qui peut la contenir : au plus $\lfloor \log_2 n \rfloor + 1$ tours, soit 20 pour un million d'éléments, quand la recherche séquentielle en fait jusqu'à $n$ . Ce chapitre d'informatique commune de première année, au programme de MPSI, PCSI, PTSI, TSI et TPC, au Maroc et en France, traite d'abord les listes Python : création, indices, tranches, alias et copies, listes de listes ; puis les parcours (somme, maximum, second maximum, comptage) et les deux recherches, avec leur variant, leur invariant et leur coût en $O(n)$ ou en $O(\log n)$ . Les exercices reprennent des questions des sujets du CNC, de CCINP, de Mines-Ponts et de X-ENS. La recherche d'un zéro d'une fonction par dichotomie, au programme de TSI et de TPC en France, y est traitée aussi.

Ce que tu sauras faire

Une liste range sous un seul nom des valeurs numérotées : les pesées d'une journée, les numéros des lots d'un registre, les cases d'une grille. Chercher une valeur dans une liste est l'une des tâches les plus fréquentes d'un programme, et presque tous les sujets d'informatique commencent par là. À la fin de ce chapitre, tu dois savoir :

créer une liste de quatre façons, en lire et en modifier les éléments, en extraire une tranche ;
prévoir l'effet d'une affectation M = L, d'une copie, d'un appel de fonction sur une liste ;
écrire une recherche séquentielle : appartenance, position, extremum, second maximum, comptage ;
comparer les paires d'éléments d'une liste par deux boucles imbriquées ;
écrire une recherche dichotomique dans une liste triée, la prouver par un variant et un invariant, et compter ses tours ;
évaluer le coût d'un programme sur une liste, coûts cachés compris, et l'écrire avec la notation $O$ ;
créer une liste de listes sans lignes liées.

L'essentiel : Prouver la dichotomie Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Variant et invariant de la dichotomie

Variant : $d - g + 1$ , nombre de cases de la zone ; entier positif tant que $g \le d$ , il diminue d'au moins 1 à chaque tour. $d - g$ est aussi un variant (positif ou nul à l'entrée de chaque tour), mais pas « positif pendant toute l'exécution » : il vaut -1 à la sortie.
Invariant : les éléments d'indice $< g$ sont $< x$ , ceux d'indice $> d$ sont $> x$ . Donc, si $x$ est dans la liste, son indice est entre $g$ et $d$ .
Tours : au plus $\lfloor \log_2 n \rfloor + 1$ ; 10 pour 1000 éléments, 20 pour $10^6$ . La version récursive du chapitre Récursivité fait au plus 21 appels pour $10^6$ : 20 avec comparaison, plus l'appel final sur une zone vide.
Précondition : liste triée.

Une méthode du chapitre Extrait gratuit

Méthode Écrire une dichotomie itérative sans erreur d'indice

Quand l’utiliser

On cherche une valeur dans une liste triée, et l'on veut un coût logarithmique ; ou l'énoncé demande « une recherche dichotomique ».

Rappel de cours

Zone L[g], ..., L[d], $d$ compris ; on boucle tant que g <= d ; milieu m = (g + d) // 2 ; on exclut le milieu examiné : g = m + 1 ou d = m - 1. Au plus $\lfloor \log_2 n \rfloor + 1$ tours.

Démarche

Vérifier que la liste est triée (précondition, dite et non testée).
Initialiser g = 0, d = len(L) - 1.
Écrire la boucle à trois cas : égal (renvoyer), plus petit (à droite), plus grand (à gauche).
Renvoyer la valeur d'absence après la boucle.
Tester la liste vide, un élément, le premier et le dernier.

Rédaction type

g = 0
d = len(L) - 1
while g <= d:
    m = (g + d) // 2
    if L[m] == x:
        return m
    elif L[m] < x:
        g = m + 1
    else:
        d = m - 1
return -1

« À chaque tour, la zone perd au moins la moitié de ses cases : au plus $\lfloor \log_2 n \rfloor + 1$ tours, coût en $O(\log n)$ . »

Exemple traité

Recherche du lot 238 dans lots : tour 1, $(g, d) = (0, 14)$ , $m = 7$ , lots[7] vaut 171, plus petit : $g = 8$ ; tour 2, $(8, 14)$ , $m = 11$ , 214, plus petit : $g = 12$ ; tour 3, $(12, 14)$ , $m = 13$ , 238 : trouvé.

print(recherche_dicho(lots, 238))

Le programme affiche :

Erreurs fréquentes

while g < d : la dernière case n'est jamais examinée.
g = m ou d = m avec while g <= d : boucle infinie quand $g = d$ .
m = (g + d) / 2 : flottant, TypeError à la lecture de L[m].
Appliquer la dichotomie à une liste non triée.

Pour s’entraîner

Exercices 21 et 24, problème 3.

Un exercice corrigé Extrait gratuit

Exercice Une dichotomie à la main ★☆☆

On considère la liste triée de 11 éléments

T = [3, 7, 12, 18, 25, 31, 36, 44, 50, 57, 63]

et la fonction recherche_dicho du cours (section 7.3).

Dresser le tableau de la recherche de 44 : pour chaque tour, les valeurs de g, d, m, T[m] et la décision prise.
Même question pour la recherche de 20, qui n'est pas dans la liste.
Combien de tours fait au plus recherche_dicho sur une liste de 11 éléments ? Donner une valeur cherchée qui réalise ce maximum.

Indications

Méthode 11 : une ligne par tour ; m = (g + d) // 2 ; on compare T[m] à la valeur cherchée et l'on jette la moitié qui ne peut pas la contenir.
La boucle s'arrête quand on trouve, ou quand la zone devient vide ( $g > d$ ).
Question 3 : la zone passe de 11 cases à au plus 5, puis 2, puis 1.

Analyse : comment trouver l’idée

Au départ, g = 0 et d = 10 : la zone contient les 11 cases. À chaque tour, la case du milieu est examinée puis retirée de la zone, avec toute la moitié du mauvais côté. On écrit l'état des variables au début de chaque tour, avant la comparaison.

Correction détaillée

Les deux tableaux suivants ont été produits par un programme qui suit l'exécution de recherche_dicho.

Recherche de 44.

tour	`g`	`d`	`m`	`T[m]`	décision
1	0	10	5	31	31 < 44 : `g = 6`
2	6	10	8	50	50 > 44 : `d = 7`
3	6	7	6	36	36 < 44 : `g = 7`
4	7	7	7	44	trouvé : renvoie 7

Recherche de 20.

tour	`g`	`d`	`m`	`T[m]`	décision
1	0	10	5	31	31 > 20 : `d = 4`
2	0	4	2	12	12 < 20 : `g = 3`
3	3	4	3	18	18 < 20 : `g = 4`
4	4	4	4	25	25 > 20 : `d = 3`
fin	4	3			zone vide : renvoie $-1$

Recherche de 20 dans la liste T : la zone de recherche, colorée, se réduit de 11 cases à 5, puis 2, puis 1, puis devient vide ; la case examinée à chaque tour est encadrée.

À la fin de la recherche de 20, on a $g = 4$ et $d = 3$ : 20 serait à insérer entre T[3] = 18 et T[4] = 25.

print(recherche_dicho(T, 44), recherche_dicho(T, 20))

Le programme affiche :

7 -1

Le nombre de cases de la zone passe de 11 à au plus 5, puis au plus 2, puis au plus 1 : au plus 4 tours, et $\lfloor \log_2 11 \rfloor + 1 = 3 + 1 = 4$ (cours, section 7.6). Les deux recherches précédentes réalisent ce maximum, 44 parce qu'il est atteint au dernier tour possible, 20 parce qu'il est absent.

Interprétation : une recherche séquentielle aurait comparé 44 aux huit premiers éléments et 20 aux onze ; la dichotomie fait 4 comparaisons dans les deux cas.

Méthodes à retenir

Une trace de dichotomie s'écrit en tableau, une ligne par tour, avec l'état au début du tour ; la recherche d'un absent finit sur $g = d + 1$ . Voir la méthode 11.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 18 méthodes, 21 pièges corrigés, la carte mentale, 35 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Les trois premiers chapitres de chaque matière sont offerts avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Une question ? WhatsApp

Plan du cours

1. Une liste pour ranger des mesures
- 1.1 Le besoin
- 1.2 Lire un élément
2. Créer une liste
- 2.1 Littérale, par répétition, par ajouts
- 2.2 Par compréhension
- 2.3 Tranches et concaténation
- 2.4 Retirer le dernier élément
3. Mutabilité, alias et copies
- 3.1 Modifier une liste en place
- 3.2 Deux noms pour une même liste
- 3.3 Copier une liste
- 3.4 Une liste passée à une fonction
4. Parcourir une liste
- 4.1 Par élément ou par indice
- 4.2 Les trois variables et la nouvelle liste
- 4.3 Ne pas modifier une liste pendant qu'on la parcourt
5. La recherche séquentielle
- 5.1 Appartenance
- 5.2 Renvoyer une position
- 5.3 Le maximum et sa position
- 5.4 Le second maximum
- 5.5 Compter
- 5.6 Terminaison et correction
- 5.7 Le coût d'une recherche et la notation $O$
6. Boucles imbriquées : comparer des paires
- 6.1 Une liste contient-elle un doublon ?
- 6.2 Les deux valeurs les plus proches
7. La recherche dichotomique
- 7.1 L'idée
- 7.2 Dérouler à la main
- 7.3 Le programme
- 7.4 Terminaison : un variant
- 7.5 Correction : un invariant
- 7.6 Combien de tours ?
- 7.7 Séquentielle ou dichotomique
- 7.8 Cas limites et jeu de tests
- 7.9 Variantes
- 7.10 Un peu d'histoire
- 7.11 Résoudre $f(x) = 0$ par dichotomie
8. Le coût des opérations sur les listes
9. Listes de listes
- 9.1 Une grille
- 9.2 Le piège des lignes liées
- 9.3 Copier une grille, chercher dans une grille
10. Compléments du programme marocain
- 10.1 Les autres méthodes des listes
- 10.2 Les indices négatifs
- 10.3 La copie profonde
- 10.4 Meilleur cas et pire cas

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Créer une liste adaptée ; créer, parcourir et copier une grille
Prévoir l'effet d'une affectation, d'une copie ou d'un appel
Choisir le parcours, et construire une nouvelle liste
Chercher un élément avec une sortie anticipée
Renvoyer une position, ou -1
Calculer un extremum, sa position, un second maximum
Compter des occurrences
Comparer les paires avec deux boucles imbriquées
Écrire une dichotomie itérative sans erreur d'indice
Adapter la dichotomie
Dérouler une dichotomie à la main
Justifier la terminaison et la correction d'une recherche
Évaluer un coût et l'écrire avec la notation $O$
Écrire un jeu de tests pour une recherche
Relire un code de recherche et trouver l'erreur
Résoudre $f(x) = 0$ par dichotomie
Employer les méthodes des listes et la copie profonde
Donner le meilleur cas et le pire cas d'une recherche

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (14)

Alias et copies : prévoir l'affichage
Un plateau sans lignes liées
Des listes vides et une liste renversée
Compter, filtrer, vérifier tous les éléments
Somme, moyenne et écart type d'une série
Le minimum et sa position
Le maximum et son premier indice
Une position, ou -1
Des entiers consécutifs
Ne pas modifier la liste reçue
Une dichotomie à la main
Les treize tests d'une dichotomie
Trois copies
Les méthodes des listes

Entraînement (17)

Le second maximum au sens strict
Le premier et le dernier passage au niveau moyen
Un polynôme rangé dans une liste
Le plus petit entier absent
Compter avec une liste de compteurs
Une liste contient-elle un doublon ?
Les deux valeurs les plus proches
Rejeter des positions, chercher sans in
Écrire et réparer une dichotomie
Où insérer une nouvelle valeur
Mesurer les deux recherches
La valeur la plus proche dans une liste triée
Construire une liste sans coût caché
Le maximum d'une grille
Un zéro par dichotomie
Meilleur cas, pire cas
Supprimer des éléments sans en sauter

Approfondissement (4)

Encadrer un seuil par dichotomie
Sélectionner dans une table triée
L'orientation d'une image par dichotomie
Le nombre exact de tours

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Simuler un feu de forêt sur une grille
CNC 2026, filière MP, épreuve d'informatique, partie II, questions 15 à 22, complétées
Le médian d'une liste
CNC 2019, filière MP, épreuve d'informatique, exercice « Médian d'une liste de nombres », questions 1 à 5, complétées
Une file de voitures codée par une liste de booléens
Mines-Ponts 2017, filières MP, PC et PSI, épreuve d'informatique commune, questions 1 à 10, 17 et 21 à 23

Questions fréquentes

Comment écrire une recherche dichotomique en Python ?

La zone de recherche va de l'indice g à l'indice d, compris : au départ g = 0 et d = len(L) - 1. Tant que g <= d, on calcule le milieu m = (g + d) // 2 ; si L[m] == x, on renvoie m ; si L[m] < x, on continue à droite avec g = m + 1 ; sinon, à gauche avec d = m - 1. Après la boucle, on renvoie -1. Le milieu se calcule avec //, car un flottant n'est pas un indice. La liste doit être triée : c'est une précondition, que la fonction ne vérifie pas. Si plusieurs éléments valent x, elle renvoie l'indice de l'un d'eux, pas forcément le premier.

Quelle est la complexité de la recherche dichotomique ?

Sur une liste de $n \geq 1$ éléments, elle fait au plus $\lfloor \log_2 n \rfloor + 1$ tours : 10 pour 1000 éléments, 20 pour un million, 30 pour un milliard. Son coût est logarithmique, en $O(\log n)$ . La recherche séquentielle fait au pire $n$ tours, quand la valeur est absente ou en dernière position : son coût est linéaire, en $O(n)$ . Le prix de la dichotomie est que la liste doit être triée ; trier coûte plus qu'une recherche séquentielle, et l'on trie une fois quand on doit ensuite chercher souvent.

Quel est le variant et l'invariant de la recherche dichotomique ?

Le variant est $d - g + 1$ , le nombre de cases de la zone : c'est un entier strictement positif tant que g <= d, et il diminue d'au moins 1 à chaque tour, puisque le milieu examiné est retiré de la zone. $d - g$ convient aussi, car il est positif ou nul à l'entrée de chaque tour, même s'il vaut $-1$ à la sortie. L'invariant est : les éléments d'indice inférieur à $g$ sont strictement plus petits que $x$ , ceux d'indice supérieur à $d$ strictement plus grands. À la sortie de la boucle, $g = d + 1$ : aucun élément ne vaut $x$ , et renvoyer $-1$ est juste.

Pourquoi M = L ne copie pas une liste en Python ?

M = L donne deux noms à une seule liste : modifier M[0] modifie L[0]. Pour obtenir une nouvelle liste, on écrit L[:] ou [x for x in L] ; c'est une copie superficielle, qui partage les sous-listes. Une grille se crée par [[0] * p for i in range(n)], jamais par [[0] * p] * n, qui répète $n$ fois la même ligne. Une fonction ne modifie la liste reçue que si sa spécification le dit. Au programme marocain, copy.deepcopy(L) copie tous les niveaux.

Comment chercher un élément dans une liste Python sans utiliser in ?

On écrit une recherche séquentielle : for i in range(len(L)), et return i dès que L[i] == x ; après la boucle, return -1. Pour un simple test d'appartenance, une boucle while i < len(L) and L[i] != x avance i, puis l'on renvoie i < len(L). L'expression x in L fait la même recherche, au même coût, jusqu'à len(L) comparaisons ; quand un sujet demande d'écrire la recherche, on écrit la boucle. En France, x in L sur une liste n'est utilisable qu'avec la documentation du sujet.

Combien coûtent les opérations sur une liste Python ?

L[i], L[i] = v, len(L) et L.pop() ont un coût constant, et L.append(x) un coût constant en moyenne. Une tranche, une copie, la concaténation +, le test x in L et la comparaison L1 == L2 coûtent un temps proportionnel au nombre d'éléments recopiés ou comparés. Écrire L = L + [x] dans une boucle de $n$ tours recopie $n(n - 1)/2$ éléments : le coût est quadratique, alors qu'avec L.append(x) il est linéaire pour la boucle entière. Au programme marocain, insert, remove, pop(i), index et count ont un coût linéaire.

Comment y accéder

Ce chapitre fait partie de l'accès complet. Les trois premiers chapitres de chaque matière (deux par bloc en économie et droit, en management et gestion) sont offerts avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.