Informatique · Première · 2 exercices vérifiés
S’entraîner : Recherche dichotomique dans un tableau trié
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Dans un tableau TRIÉ, on compare la valeur cherchée à l'élément du milieu et on poursuit dans la moitié qui peut la contenir ; la largeur de l'intervalle de recherche (variant de boucle) diminue strictement à chaque tour, ce qui prouve la terminaison ; le nombre de tours est au plus ⌊log₂ n⌋ + 1, soit un coût logarithmique, contre un coût linéaire pour le parcours séquentiel.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Parcours séquentiel d'un tableau — Parcourir un tableau élément par élément pour rechercher une occurrence, un extremum (maximum, minimum) ou calculer une moyenne ; le coût est linéaire : le nombre d'opérations est proportionnel à la longueur du tableau, et une recherche d'occurrence examine tout le tableau dans le pire cas.
- Nombre de bits d'un entier, d'une somme, d'un produit — Nombre de bits nécessaires pour écrire un entier naturel n en base 2 (le plus petit k tel que n < 2^k) ; plus grand entier représentable sur k bits (2^k − 1) ; une somme de deux entiers de k bits tient sur k + 1 bits, un produit sur 2k bits ; tailles courantes des entiers (8, 16, 32 ou 64 bits) ; entiers de taille arbitraire de Python.
Comment se déroule la séance
Cette séance s’appuie sur 2 exercices vérifiés. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Réponse numérique (2). Difficulté 3 sur 5. Environ 8 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 3 sur 5 · ≈ 5 minutes
Énoncé
On exécute le programme Python ci-dessous (recherche dichotomique dans un tableau trié). La variable n compte les tours de boucle.
| n° | Instruction |
|---|---|
| 1 | def recherche(t, v): |
| 2 | ····debut = 0 |
| 3 | ····fin = len(t) - 1 |
| 4 | ····n = 0 |
| 5 | ····while debut <= fin: |
| 6 | ········n = n + 1 |
| 7 | ········milieu = (debut + fin) // 2 |
| 8 | ········if t[milieu] == v: |
| 9 | ············return n |
| 10 | ········elif t[milieu] < v: |
| 11 | ············debut = milieu + 1 |
| 12 | ········else: |
| 13 | ············fin = milieu - 1 |
| 14 | ····return n |
| 15 | print(recherche([13, 17, 20, 21, 27, 30, 33, 34, 40], 7)) |
Chaque groupe de quatre points « ···· » marque un niveau d'indentation (quatre espaces en Python).
Quel nombre ce programme affiche-t-il ?
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.