TS-DAlgorithmes de tri

Recherche dichotomique : justifier le tableau trié, compléter la version itérative, variante récursive et position d'insertion

Idée directrice

Dès que le tableau est trié — et le sujet fait justifier cette caractéristique —, on compare x à la case du milieu et on élimine la moitié qui ne peut pas le contenir. On complète l'algorithme à trous (bornes 0 et N − 1, milieu, réduction de la partie, arrêt « trouvé ou partie vide »), on le trace passage par passage, puis on le transforme : position d'insertion (première case strictement supérieure), version récursive, découpage en trois parties. Le sujet commun aux sections Mathématiques, Sciences expérimentales et Techniques fait compléter la version itérative (2026) ; les variantes récursives et trichotomiques viennent des sujets de la section Sciences de l'informatique.

Ce qui aide à reconnaître la démarche

« Quelle caractéristique présente le tableau T pour privilégier la recherche dichotomique à la recherche séquentielle ? » ; « Compléter l'algorithme suivant de la fonction booléenne RechDicho qui exploite le principe de la méthode de recherche dichotomique » ; « Quel est le rôle de la variable P » ; « utilise la recherche dichotomique pour déterminer la position d'insertion » ; « on peut utiliser une méthode de recherche dite Trichotomique » ; « Déduire le rôle de la fonction Quoi »

Besoin d’un point de départ ? Voir la méthode

Avant de choisir la dichotomie, vérifier que le tableau est trié (contrôle de saisie T[i] > T[i−1], remplissage par une suite croissante, tri préalable) ; sinon, recherche séquentielle.
Indices à partir de 0 : g ← 0, d ← N − 1, m ← (g + d) Div 2 ; réduire par d ← m − 1 ou g ← m + 1, jamais par m seul.
Arrêt : trouvé OU g > d ; la valeur retournée (booléen, indice ou −1) doit être juste dans les deux cas.
Position d'insertion : supprimer l'arrêt « trouvé », envoyer l'égalité à droite et retourner g, qui vaut N si x ≥ T[N−1].
Version récursive : cas d'arrêt g > d en premier, puis un seul appel sur la bonne moitié ; appel initial (T, 0, N − 1, x). Trace : une ligne par passage (m, T[m], g, d), au plus $\lfloor \log_2 N \rfloor + 1$ passages.

Les pièges à vérifier dans ta démarche

Écrire d ← N (lecture de T[N], au-delà de la dernière case remplie T[N − 1]) ou d ← m (boucle infinie pour certaines valeurs absentes, par exemple x < T[0]) ; tester g < d au lieu de g ≤ d (la dernière case candidate n'est jamais comparée) ; confondre « première case ≥ x » et « première case > x » dans la position d'insertion (x = 24 donne 5, pas 4) ; appliquer la dichotomie à un tableau non trié ; dans la version récursive, lire T[m] avant d'avoir testé la partie vide ; oublier la borne N quand x dépasse la dernière case.

Sujet principal

Exercice 2 (5 points) — dans l'esprit des sessions principales 2021 et 2026

5 questionsCorrigé masqué

Soit TAB un nouveau type tableau de 100 entiers. On considère la procédure Saisie suivante, qui remplit un tableau T de type TAB par N entiers (5 ≤ N ≤ 100) :

Procédure Saisie (@T : TAB, N : Entier)
DEBUT
   Répéter
      Ecrire("T[0] = ")
      Lire(T[0])
   Jusqu'à T[0] ≥ 0
   Pour i de 1 à N-1 Faire
      Répéter
         Ecrire("T[", i, "] = ")
         Lire(T[i])
      Jusqu'à T[i] > T[i-1]
   Fin Pour
FIN

On se propose de vérifier si un entier x donné figure dans le tableau T ainsi rempli, puis de déterminer où il faudrait l'insérer.

Fonction Existe (à compléter à la question 2) :

Fonction Existe (T : TAB, N, x : Entier)
                : Booléen
DEBUT
   g ← ……
   d ← ……
   Répéter
      m ← ……………
      Si T[m] < x Alors
         ……………
      Sinon Si T[m] > x Alors
         ……………
      FinSi
   Jusqu'à (T[m] = x) Ou (……………)
   Retourner ……………
FIN

T.D.O.L. de Existe : Objet …… | Type/Nature ……

Tableau T utilisé aux questions 3 et 4 (N = 9) :

indice :  0  1  2  3  4  5  6  7  8
T      :  3  8 11 17 24 30 36 45 52

Travail demandé :

Concernant la procédure Saisie :
1. Donner le rôle de la procédure Saisie.
2. Quelle caractéristique présente le tableau T rempli par Saisie pour privilégier la recherche dichotomique à la recherche séquentielle ?
3. Un élève affirme qu'on peut appliquer la recherche dichotomique à un tableau quelconque, sans le trier au préalable. Corriger cette affirmation.
Compléter l'algorithme de la fonction booléenne Existe, qui exploite le principe de la recherche dichotomique pour vérifier si x figure dans T, puis compléter son T.D.O.L.
On exécute Existe(T, 9, x) avec le tableau T ci-dessus.
1. Pour x = 45, donner les valeurs successives de g, d et m à chaque passage dans la boucle, et la valeur retournée.
2. Même question pour x = 20.
3. Pour un tableau de N = 100 entiers, combien de passages dans la boucle la fonction Existe effectue-t-elle au plus ? Combien de comparaisons avec x une recherche séquentielle peut-elle demander ?
On se propose d'écrire une fonction PosInsert(T, N, x) qui retourne la position d'insertion de x, c'est-à-dire l'indice de la première case de T dont le contenu est strictement supérieur à x : c'est là qu'il faudrait insérer x pour que T reste dans l'ordre croissant. La valeur retournée doit être égale à N pour toute valeur de x ≥ T[N−1].
1. Pour le tableau T ci-dessus, donner la valeur retournée par PosInsert pour x = 20, x = 24 et x = 60.
2. En modifiant la fonction Existe, écrire l'algorithme de la fonction PosInsert, sans parcours séquentiel du tableau, et dresser son T.D.O.L.
(Section Sciences de l'informatique — approfondissement ; les autres sections peuvent s'arrêter à la question 4.) Écrire l'algorithme d'une fonction récursive RechRec(T, g, d, x) qui retourne Vrai si x figure dans la partie de T délimitée par les indices g et d, Faux sinon, selon le même principe. Donner l'instruction qui remplace Existe(T, N, x).

N.B. Les cases d'un tableau sont indicées à partir de 0.

Voir la correction commentéeAprès avoir posé votre démarche

1.a Idée : lire la condition d'arrêt de chaque boucle Répéter. La procédure Saisie remplit T par N entiers : le premier positif ou nul, chacun des suivants strictement supérieur au précédent ; la saisie d'une case est reprise tant que cette condition n'est pas vérifiée.

1.b Le tableau T est trié dans l'ordre strictement croissant : T[i] > T[i−1] pour tout i de 1 à N−1. Comparer x à la case du milieu permet alors d'écarter toute une moitié du tableau (si T[m] > x, x ne peut se trouver qu'à gauche de m).

1.c L'affirmation est fausse : la recherche dichotomique s'applique à un tableau trié ; un tableau quelconque doit d'abord être trié, sinon on utilise la recherche séquentielle, applicable à tout tableau. Sur un tableau non trié, la comparaison avec la case du milieu ne dit plus de quel côté se trouve x : écarter une moitié peut écarter justement la case qui le contient.

2. Idée : la partie [g, d] contient toujours les cases où x peut encore se trouver ; elle part du tableau entier (indices 0 à N − 1) et exclut à chaque passage le milieu déjà comparé.

Fonction Existe (T : TAB, N, x : Entier)
                : Booléen
DEBUT
   g ← 0
   d ← N - 1
   Répéter
      m ← (g + d) Div 2
      Si T[m] < x Alors
         g ← m + 1
      Sinon Si T[m] > x Alors
         d ← m - 1
      FinSi
   Jusqu'à (T[m] = x) Ou (g > d)
   Retourner T[m] = x
FIN

T.D.O.L. de Existe : g, d, m — Type/Nature : Entier.

La boucle Répéter s'exécute au moins une fois, ce qui est possible puisque N ≥ 5. À la sortie, soit T[m] = x, soit g > d (partie vide) et alors T[m] ≠ x : retourner la valeur de l'expression T[m] = x donne la bonne réponse dans les deux cas.

3.a Idée : une ligne par passage, avec les bornes après la mise à jour.

passage   m  T[m]   g   d
début     -    -    0   8
1         4   24    5   8
2         6   36    7   8
3         7   45    7   8

T[7] = 45 = x : arrêt après 3 passages, Existe retourne $\boxed{\text{Vrai}}$ .

3.b

passage   m  T[m]   g   d
début     -    -    0   8
1         4   24    0   3
2         1    8    2   3
3         2   11    3   3
4         3   17    4   3

Après le 4ᵉ passage, g = 4 > d = 3 : la partie est vide. T[3] = 17 ≠ 20, Existe retourne $\boxed{\text{Faux}}$ ; 20 se placerait entre T[3] = 17 et T[4] = 24.

3.c Idée : un passage sans succès laisse au plus la moitié des cases restantes. Sur k cases restantes, il en reste au plus k Div 2 : 100, 50, 25, 12, 6, 3, 1. Le septième passage examine la dernière case possible, d'où au plus $\boxed{7}$ passages ( $2^6 \le 100 < 2^7$ ). Une recherche séquentielle peut demander 100 comparaisons (x absent ou dans la dernière case).

4.a Idée : chercher la première case strictement supérieure à x.

x = 20 : la première case > 20 est T[4] = 24, d'où $\boxed{4}$ .
x = 24 : T[4] = 24 n'est pas strictement supérieur à 24 ; la première case > 24 est T[5] = 30, d'où $\boxed{5}$ .
x = 60 ≥ T[8] = 52 : aucune case ne convient, PosInsert retourne N, soit $\boxed{9}$ .

4.b Idée : on ne s'arrête plus quand T[m] = x ; une case égale à x n'est pas « strictement supérieure », on continue donc à droite. La boucle ne s'arrête que sur la partie vide ; alors g = d + 1, toutes les cases d'indice inférieur à g contiennent une valeur ≤ x et toutes celles d'indice supérieur à d une valeur > x : g est la position cherchée.

Fonction PosInsert (T : TAB,
         N, x : Entier) : Entier
DEBUT
   g ← 0
   d ← N - 1
   Tant que g ≤ d Faire
      m ← (g + d) Div 2
      Si T[m] > x Alors
         d ← m - 1
      Sinon
         g ← m + 1
      FinSi
   Fin Tant que
   Retourner g
FIN

T.D.O.L. de PosInsert : g, d, m — Type/Nature : Entier.

Contrôle sur T : pour x = 24, m prend les valeurs 4 (24 ≤ 24, g = 5), 6 (36 > 24, d = 5) puis 5 (30 > 24, d = 4) et la fonction retourne 5. Pour x = 60, g passe à 5, 7, 8 puis 9 = N : la valeur exigée pour x ≥ T[N−1] est obtenue sans cas particulier.

5. Idée : deux cas d'arrêt — partie vide (Faux) ou milieu égal à x (Vrai) ; sinon un seul appel récursif, sur la moitié qui peut contenir x. Le test g > d vient en premier : sur une partie vide, on ne lit aucune case.

Fonction RechRec (T : TAB,
         g, d, x : Entier) : Booléen
DEBUT
   Si g > d Alors
      Retourner Faux
   Sinon
      m ← (g + d) Div 2
      Si T[m] = x Alors
         Retourner Vrai
      Sinon Si T[m] > x Alors
         Retourner RechRec(T, g, m-1, x)
      Sinon
         Retourner RechRec(T, m+1, d, x)
      FinSi
   FinSi
FIN

T.D.O.L. de RechRec : m — Type/Nature : Entier.

L'instruction RechRec(T, 0, N-1, x) remplace Existe(T, N, x). Pour x = 20, les appels portent sur (g, d) = (0, 8), (0, 3), (2, 3), (3, 3), puis (4, 3), qui retourne Faux.

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Variantes rencontrées : proposition fausse à corriger « la recherche dichotomique est une méthode de recherche appliquée sur un tableau quelconque » (principale 2017) ; rôle de la variable P, position du premier élément strictement supérieur à a par parcours séquentiel, puis borne n + 1 à garantir (principale 2021) ; recherche séquentielle retournant l'indice ou −1, réécrite en Tant que puis en recherche symétrique par rapport au milieu (principale 2024) ; caractéristique du tableau puis fonction booléenne RechDicho à compléter (principale 2026). En section Sciences de l'informatique : fonction récursive Dichotomie donnant la position d'insertion d'un tri par insertion dichotomique (contrôle 2018), fonction récursive inconnue à identifier (contrôle 2019), recherche trichotomique récursive (principale 2022).

Exercices d'entraînement — une nuance à la fois

1 Drill TS-D.1 — Séquentielle ou dichotomique : coût d'une recherche et complexité

Entraînement 01 / 05

Drill TS-D.1 — Séquentielle ou dichotomique : coût d'une recherche et complexité

3 questionsCorrigé masqué

On considère un tableau T de N = 16 entiers trié dans l'ordre croissant :

indice :  0  1  2  3  4  5  6  7
T      :  2  5  9 12 15 21 26 30

indice :  8  9 10 11 12 13 14 15
T      : 34 41 47 50 58 63 71 80

et deux fonctions qui retournent l'indice de la case de T contenant x, ou −1 si x ne figure pas dans T :

Fonction RechSeq (T : TAB,
         N, x : Entier) : Entier
DEBUT
   i ← 0
   Tant que (i < N-1)
            Et (T[i] ≠ x) Faire
      i ← i + 1
   Fin Tant que
   Si T[i] = x Alors
      Retourner i
   Sinon
      Retourner -1
   FinSi
FIN

Fonction RechDich (T : TAB,
         N, x : Entier) : Entier
DEBUT
   g ← 0
   d ← N - 1
   p ← -1
   Tant que (g ≤ d) Et (p = -1) Faire
      m ← (g + d) Div 2
      Si T[m] = x Alors
         p ← m
      Sinon Si T[m] > x Alors
         d ← m - 1
      Sinon
         g ← m + 1
      FinSi
   Fin Tant que
   Retourner p
FIN

On mesure le coût d'une recherche par le nombre de cases de T comparées à x ; une case soumise à plusieurs comparaisons compte une seule fois. Pour RechDich, c'est le nombre de passages dans la boucle.

Pour x = 47, x = 2, x = 80 et x = 44, donner la valeur retournée par chaque fonction et son coût.
Donner le coût maximal de chaque fonction pour N = 16, N = 100 et N = 1000. En déduire la complexité de chaque méthode (ordre de grandeur du coût en fonction de N).
On applique RechDich au tableau non trié T = [12, 3, 25, 7, 18] (N = 5) avec x = 3. Quelle valeur retourne-t-elle ? Que retournerait RechSeq ? Conclure.

N.B. Les cases d'un tableau sont indicées à partir de 0.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : RechSeq compare les cases une à une depuis l'indice 0 ; RechDich ne compare que les milieux successifs.

  x    RechSeq      RechDich
 47   10 (coût 11)  10 (coût 4)
  2    0 (coût 1)    0 (coût 4)
 80   15 (coût 16)  15 (coût 5)
 44   -1 (coût 16)  -1 (coût 4)

RechSeq : x trouvé à l'indice p coûte p + 1 ; x absent coûte 16 (toutes les cases).
RechDich, milieux comparés : x = 47 → 7, 11, 9, 10 ; x = 2 → 7, 3, 1, 0 ; x = 80 → 7, 11, 13, 14, 15 ; x = 44 → 7, 11, 9, 10, puis g = 10 > d = 9 et la fonction retourne −1.

Pour x = 2, RechSeq est plus rapide : la dichotomie n'améliore pas chaque recherche, elle améliore le pire cas.

2. Idée : un passage sans succès laisse au plus la moitié des cases, donc RechDich fait au plus k passages quand $2^{k-1} \le N < 2^k$ .

N = 16 : RechSeq $\boxed{16}$ , RechDich $\boxed{5}$ ( $2^4 \le 16 < 2^5$ ).
N = 100 : RechSeq $\boxed{100}$ , RechDich $\boxed{7}$ .
N = 1000 : RechSeq $\boxed{1000}$ , RechDich $\boxed{10}$ ( $2^9 \le 1000 < 2^{10}$ ).

Le coût de la recherche séquentielle est proportionnel à N ; celui de la recherche dichotomique à $\log_2 N$ : multiplier N par 10 ajoute environ 3 passages.

3. RechDich : m = 2, T[2] = 25 > 3, d = 1 ; m = 0, T[0] = 12 > 3, d = −1 ; la partie est vide et la fonction retourne $\boxed{-1}$ , alors que 3 est dans la case 1. RechSeq retourne 1 (coût 2). La dichotomie suppose un tableau trié : sinon, l'élimination d'une moitié peut écarter justement la case qui contient x.

2 Drill TS-D.2 — Tri par insertion dichotomique : placer les appels récursifs de PosIns

Entraînement 02 / 05

Drill TS-D.2 — Tri par insertion dichotomique : placer les appels récursifs de PosIns

4 questionsCorrigé masqué

Le tri par insertion dichotomique reprend le principe du tri par insertion : pour i de 1 à N − 1, on sauvegarde T[i], on cherche sa position d'insertion dans la partie T[0..i−1], déjà triée dans l'ordre croissant, on décale d'une case vers la droite les valeurs situées entre cette position et i − 1, puis on insère. La position d'insertion est cherchée de façon dichotomique, avec la fonction récursive incomplète PosIns ci-dessous, qui retourne la position d'insertion d'un entier k dans la partie triée de T délimitée par les indices g et d.

Fonction PosIns (T : TAB,
         g, d, k : Entier) : Entier
DEBUT
   ……………………………………
   Si g > d Alors
      Retourner g
   Sinon Si T[m] = k Alors
      Retourner m
   Sinon Si T[m] > k Alors
      ……………………………………
   Sinon
      ……………………………………
   FinSi
FIN

Instructions à placer :

Retourner PosIns(T, m+1, d, k)
m ← (g + d) Div 2
Retourner PosIns(T, g, m-1, k)

Réécrire la fonction PosIns en plaçant chacune des trois instructions au bon endroit.
Pour T = [3, 9, 14, 20, 31] (indices 0 à 4), donner les appels successifs et la valeur retournée par PosIns(T, 0, 4, 25), puis par PosIns(T, 0, 4, 1).
En utilisant PosIns, écrire l'algorithme de la procédure TriInsDicho(@T : TAB, N : Entier) qui permet de trier le tableau T dans l'ordre croissant par insertion dichotomique, le décalage étant confié à une procédure Decaler à écrire aussi. Dresser leurs T.D.O.L.
Pour T = [17, 5, 23, 11, 8] (N = 5), donner la position d'insertion trouvée et le contenu de T après chaque valeur de i.

N.B. Les cases d'un tableau sont indicées à partir de 0.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : le milieu doit être calculé avant d'être lu ; si T[m] > k, la position est dans la moitié gauche (appel sur g..m−1), sinon dans la moitié droite (appel sur m+1..d).

Fonction PosIns (T : TAB,
         g, d, k : Entier) : Entier
DEBUT
   m ← (g + d) Div 2
   Si g > d Alors
      Retourner g
   Sinon Si T[m] = k Alors
      Retourner m
   Sinon Si T[m] > k Alors
      Retourner PosIns(T, g, m-1, k)
   Sinon
      Retourner PosIns(T, m+1, d, k)
   FinSi
FIN

Quand g > d, m est calculé mais T[m] n'est jamais lu : la fonction retourne g, la frontière entre les valeurs inférieures et supérieures à k.

2. Avec T = [3, 9, 14, 20, 31] :

k = 25 : PosIns(T, 0, 4, 25) — m = 2, 14 < 25 — appelle PosIns(T, 3, 4, 25) — m = 3, 20 < 25 — qui appelle PosIns(T, 4, 4, 25) — m = 4, 31 > 25 — qui appelle PosIns(T, 4, 3, 25) : g > d, retour $\boxed{4}$ .
k = 1 : PosIns(T, 0, 4, 1) — m = 2, 14 > 1 — appelle PosIns(T, 0, 1, 1) — m = 0, 3 > 1 — qui appelle PosIns(T, 0, −1, 1) : retour $\boxed{0}$ .

3. Idée : sauvegarder T[i] avant le décalage, qui l'écrase ; décaler de droite à gauche pour ne perdre aucune valeur ; ne rien faire si T[i] est déjà à sa place (p = i).

Procédure TriInsDicho (@T : TAB,
                       N : Entier)
DEBUT
   Pour i de 1 à N-1 Faire
      x ← T[i]
      p ← PosIns(T, 0, i-1, x)
      Si p < i Alors
         Decaler(T, p, i-1)
         T[p] ← x
      FinSi
   Fin Pour
FIN

T.D.O.L. de TriInsDicho : i, p, x — Type/Nature : Entier (compteur, position d'insertion, valeur sauvegardée) ; PosIns — Fonction ; Decaler — Procédure.

Procédure Decaler (@T : TAB,
                   deb, fin : Entier)
DEBUT
   Pour j de fin à deb (pas = -1) Faire
      T[j+1] ← T[j]
   Fin Pour
FIN

T.D.O.L. de Decaler : j — Type/Nature : Entier.

4. Idée : à l'étape i, la recherche se fait dans T[0..i−1], déjà triée.

 i   x   p   T après l'étape
 1   5   0   5 17 23 11  8
 2  23   2   5 17 23 11  8
 3  11   1   5 11 17 23  8
 4   8   1   5  8 11 17 23

À l'étape i = 2, p = 2 = i : 23 est déjà à sa place, aucun décalage. Le tableau final est $\boxed{[5, 8, 11, 17, 23]}$ .

3 Drill TS-D.3 — Recherche trichotomique : deux pivots, trois parties, fonction récursive

Entraînement 03 / 05

Drill TS-D.3 — Recherche trichotomique : deux pivots, trois parties, fonction récursive

8 questionsCorrigé masqué

Soit T un tableau de N entiers trié dans l'ordre croissant. Pour chercher un entier x entre les indices d et f, la recherche trichotomique découpe la partie en trois à l'aide de deux pivots :

p_1 = d + (f - d)\ \text{Div}\ 3

p_2 = f - (f - d)\ \text{Div}\ 3

si d > f, la partie est vide : x ne figure pas dans T ;
si x = T[p1] ou x = T[p2], la recherche est terminée ;
si x < T[p1], on passe à la partie gauche (indices d à p1 − 1) ;
sinon, si x < T[p2], on passe à la partie du milieu (indices p1 + 1 à p2 − 1) ;
sinon, on passe à la partie droite (indices p2 + 1 à f).

On donne le tableau T suivant (N = 10) :

indice :  0  1  2  3  4  5  6  7  8  9
T      : -8 -3  0  4  9 13 18 25 31 40

Pour x = 25 puis pour x = 5, donner les valeurs successives de d, f, p1 et p2, et le résultat de la recherche.
Écrire l'algorithme d'une fonction récursive RechTri(T, d, f, x) qui retourne Vrai si x figure dans T entre les indices d et f, Faux sinon, selon ce principe. Donner l'instruction qui cherche x dans tout le tableau.
Pour x = 45, la partie devient vide avec d = 10 et f = 9. Expliquer pourquoi le test « d > f » doit précéder toute comparaison de x avec T[p1] ou T[p2].

N.B. Les cases d'un tableau sont indicées à partir de 0.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : calculer les deux pivots, comparer x aux deux cases, puis garder une seule des trois parties.

Pour x = 25 :

  d   f  p1  p2  T[p1]  T[p2]
  0   9   3   6     4     18
  7   9   7   9    25     40

25 > T[6] = 18 : partie droite, d = 7 ; puis p1 = 7 + 2 Div 3 = 7 et T[7] = 25 = x : la recherche réussit, résultat $\boxed{\text{Vrai}}$ .

Pour x = 5 :

  d   f  p1  p2  T[p1]  T[p2]
  0   9   3   6     4     18
  4   5   4   5     9     13
  4   3   (partie vide)

T[3] = 4 < 5 < T[6] = 18 : partie du milieu, indices 4 à 5. Puis 5 < T[4] = 9 : partie gauche, indices 4 à 3, vide ; résultat $\boxed{\text{Faux}}$ .

2. Idée : le cas « partie vide » est le premier cas d'arrêt, le cas « trouvé » le second ; chacun des trois autres cas relance la recherche sur une seule partie.

Fonction RechTri (T : TAB,
                  d, f, x : Entier)
                  : Booléen
DEBUT
  Si d > f Alors
    Retourner Faux
  Sinon
    p1 ← d + (f - d) Div 3
    p2 ← f - (f - d) Div 3
    Si (x = T[p1]) Ou (x = T[p2]) Alors
      Retourner Vrai
    Sinon Si x < T[p1] Alors
      Retourner RechTri(T, d, p1-1, x)
    Sinon Si x < T[p2] Alors
      Retourner RechTri(T, p1+1, p2-1, x)
    Sinon
      Retourner RechTri(T, p2+1, f, x)
    FinSi
  FinSi
FIN

T.D.O.L. de RechTri : p1, p2 — Type/Nature : Entier. Instruction pour tout le tableau : RechTri(T, 0, N-1, x).

3. Pour x = 45 : 45 > T[6] = 18, d = 7 ; puis 45 > T[9] = 40, d = 10. La partie ne contient plus aucune case et d = 10 = N ne désigne aucune case du tableau. Les pivots n'ont plus de sens : f − d = −1 et, selon la convention de Div sur les négatifs, p1 ou p2 vaut 10, une lecture hors du tableau. Tester d'abord d > f, c'est traiter le cas « x ne figure pas dans T » avant toute lecture.

4 Drill TS-D.4 — Fonction récursive inconnue : type de retour, appels successifs, rôle

Entraînement 04 / 05

Drill TS-D.4 — Fonction récursive inconnue : type de retour, appels successifs, rôle

4 questionsCorrigé masqué

Soit la fonction récursive Mystere suivante, où T est un tableau d'entiers trié dans l'ordre croissant :

Fonction Mystere (T : TAB,
                  a, g, d : Entier) : ……
DEBUT
  Si g > d Alors
    Retourner -1
  Sinon
    m ← (g + d) Div 2
    Si T[m] = a Alors
      Retourner m
    Sinon Si T[m] < a Alors
      Retourner Mystere(T, a, m+1, d)
    Sinon
      Retourner Mystere(T, a, g, m-1)
    FinSi
  FinSi
FIN

Compléter l'en-tête de la fonction Mystere par son type de retour.
Pour T = [−4, 0, 7, 12, 19, 26, 33] (indices 0 à 6), donner les appels successifs et la valeur retournée par Mystere(T, 26, 0, 6), puis par Mystere(T, 10, 0, 6), en indiquant à chaque appel la comparaison qui fait passer la recherche à la moitié gauche ou à la moitié droite.
Déduire le rôle de la fonction Mystere.
Pour ce tableau de 7 cases, combien d'appels de Mystere (appel initial compris) faut-il au plus ? Pour quelles valeurs de a ce nombre d'appels est-il atteint ?

N.B. Les cases d'un tableau sont indicées à partir de 0.

Voir la correction commentéeAprès avoir posé votre démarche

1. La fonction retourne soit −1, soit l'indice m : son type de retour est $\boxed{\text{Entier}}$ .

2. Idée : à chaque appel, calculer m puis comparer T[m] à a ; l'appel suivant porte sur la moitié droite si T[m] < a, sur la moitié gauche si T[m] > a.

Mystere(T, 26, 0, 6) : m = 3, T[3] = 12 < 26, appel Mystere(T, 26, 4, 6) : m = 5, T[5] = 26 = a, retour $\boxed{5}$ (2 appels).
Mystere(T, 10, 0, 6) : m = 3, T[3] = 12 > 10, appel Mystere(T, 10, 0, 2) : m = 1, T[1] = 0 < 10, appel Mystere(T, 10, 2, 2) : m = 2, T[2] = 7 < 10, appel Mystere(T, 10, 3, 2) : g > d, retour $\boxed{-1}$ (4 appels).

3. La fonction Mystere retourne l'indice de la case de T contenant a entre les indices g et d, ou −1 si a n'y figure pas : c'est une recherche dichotomique récursive, qui divise par deux la partie examinée à chaque appel.

4. Idée : 7 cases se répartissent en 3 à gauche, le milieu, 3 à droite ; puis 1, 1, 1. Une valeur présente est trouvée en au plus 3 appels (T[3] en 1 appel ; T[1], T[5] en 2 ; T[0], T[2], T[4], T[6] en 3). Une valeur absente épuise les trois niveaux puis fait un dernier appel sur une partie vide : au plus $\boxed{4}$ appels, atteint pour toute valeur de a absente de T.

5 Drill TS-D.5 — Bornes et indices : trouver la ligne fausse d'une recherche dichotomique

Entraînement 05 / 05

Drill TS-D.5 — Bornes et indices : trouver la ligne fausse d'une recherche dichotomique

6 questionsCorrigé masqué

On considère le tableau T de N = 6 entiers trié dans l'ordre croissant :

indice :  0  1  2  3  4  5
T      :  4  9 15 22 30 41

et la version correcte de la recherche dichotomique booléenne, avec des indices de 0 à N − 1 :

Fonction Existe (T : TAB, N, x : Entier)
                : Booléen
DEBUT
   g ← 0
   d ← N - 1
   trouve ← Faux
   Tant que (g ≤ d) Et Non(trouve) Faire
      m ← (g + d) Div 2
      Si T[m] = x Alors
         trouve ← Vrai
      Sinon Si T[m] > x Alors
         d ← m - 1
      Sinon
         g ← m + 1
      FinSi
   Fin Tant que
   Retourner trouve
FIN

Trois élèves ont modifié une seule ligne de cet algorithme :

Version A : d ← N au lieu de d ← N - 1 ;
Version B : Tant que (g < d) Et Non(trouve) Faire au lieu de g ≤ d ;
Version C : d ← m au lieu de d ← m - 1.

Pour chaque version, trouver une valeur de x pour laquelle elle échoue sur ce tableau, en donnant les valeurs successives de g, d et m et le résultat de chaque comparaison, et dire ce qui se passe : lecture hors du tableau, résultat faux ou boucle infinie.
Donner toutes les valeurs de T que la version B ne trouve pas. Qu'ont en commun ces cases ?
Un quatrième élève écrit g ← m au lieu de g ← m + 1. Trouver une valeur de x qui provoque une boucle infinie, et expliquer pourquoi la division entière Div rend g ← m et d ← m dangereuses.

N.B. Les cases d'un tableau sont indicées à partir de 0.

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : tester chaque version sur les cas limites — x plus grand que tout, x dans une partie réduite à une case, x plus petit que tout.

Version A, x = 50 (plus grand que T[5]) :

 g   d   m  T[m]
 0   6   3   22    22 < 50 : g ← 4
 4   6   5   41    41 < 50 : g ← 6
 6   6   6   ?     T[6] hors du tableau

La fonction lit T[6], hors du tableau : la dernière case a l'indice N − 1 = 5. Correction : d ← N - 1.

Version B, x = 41 :

 g   d   m  T[m]
 0   5   2   15    15 < 41 : g ← 3
 3   5   4   30    30 < 41 : g ← 5
 5   5   -   -     g < d faux : arrêt

La partie restante contient encore la case 5, qui vaut 41, mais la boucle s'arrête : résultat faux (Faux au lieu de Vrai). Correction : Tant que (g ≤ d) Et Non(trouve).

Version C, x = 3 (plus petit que T[0]) :

 g   d   m  T[m]
 0   5   2   15    15 > 3 : d ← 2
 0   2   1    9     9 > 3 : d ← 1
 0   1   0    4     4 > 3 : d ← 0
 0   0   0    4     4 > 3 : d ← 0 …

Quand g = d, m = d et d ← m ne change plus rien : boucle infinie. Correction : d ← m - 1.

2. La version B ne trouve pas 9, 22 et 41 (indices 1, 3 et 5) : ce sont les cases qu'on n'atteint que lorsque la partie est réduite à cette seule case (g = d), et la condition g < d arrête alors la boucle sans la comparer à x.

3. Avec g ← m et x = 50 :

 g   d   m  T[m]
 0   5   2   15    15 < 50 : g ← 2
 2   5   3   22    22 < 50 : g ← 3
 3   5   4   30    30 < 50 : g ← 4
 4   5   4   30    30 < 50 : g ← 4 …

Idée : m = (g + d) Div 2 est arrondi vers le bas, donc m = g dès que d = g + 1, et m = d dès que g = d. Dans ces cas, g ← m (ou d ← m) laisse la partie inchangée et la boucle tourne sans fin. Retirer m de la partie — g ← m + 1, d ← m - 1 — garantit qu'elle perd au moins une case à chaque passage.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Recherche dichotomique : justifier le tableau trié, compléter la version itérative, variante récursive et position d'insertion

Exercice 2 (5 points) — dans l'esprit des sessions principales 2021 et 2026

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Drill TS-D.1 — Séquentielle ou dichotomique : coût d'une recherche et complexité

Drill TS-D.2 — Tri par insertion dichotomique : placer les appels récursifs de PosIns

Drill TS-D.3 — Recherche trichotomique : deux pivots, trois parties, fonction récursive

Drill TS-D.4 — Fonction récursive inconnue : type de retour, appels successifs, rôle

Drill TS-D.5 — Bornes et indices : trouver la ligne fausse d'une recherche dichotomique

Relier ce raisonnement au bac