Énoncé
Saisir N avec 1 ≤ N ≤ 100, puis remplir un tableau T de N entiers triés par ordre croissant. Saisir un entier Cible. Écrire une fonction Dichotomie qui retourne un indice de Cible dans T, ou −1 si elle est absente. Afficher le résultat.
Exemples et cas limites
Saisissez ces valeurs dans la console pour vérifier votre résultat :
Saisir N, puis les N entiers par ordre croissant, puis Cible. Une valeur inférieure à la précédente est redemandée ; les doublons sont acceptés.
Entrée
N = 5 t[0] = 1 t[1] = 3 t[2] = 5 t[3] = 8 t[4] = 12 Cible = 8
Sortie attendue
3
Entrée
N = 3 t[0] = -4 t[1] = 0 t[2] = 2 Cible = -4
Sortie attendue
0
Entrée
N = 1 t[0] = 5 Cible = 6
Sortie attendue
-1
Complétez les modules marqués par un commentaire dans le code de départ. Les modules déjà écrits permettent de saisir vos données. Exécutez les cas de test et comparez la sortie attendue, ou ouvrez directement l’onglet Correction.
Code algorithmique
| 1 | algorithme recherche_dichotomique |
| 2 | debut |
| 3 | saisir(n) |
| 4 | remplir(t, n) |
| 5 | saisircible(cible) |
| 6 | indice ← dichotomie(t, n, cible) |
| 7 | afficher(indice) |
| 8 | fin |
| 9 | |
| 10 | procedure saisir(@n : entier) |
| 11 | debut |
| 12 | repeter |
| 13 | ecrire("N = ") |
| 14 | lire(n) |
| 15 | jusqua 1 ≤ n ≤ 100 |
| 16 | fin |
| 17 | |
| 18 | procedure remplir(@t : tab, n : entier) |
| 19 | debut |
| 20 | pour i de 0 à n - 1 faire |
| 21 | repeter |
| 22 | ecrire("t[" + convch(i) + "] = ") |
| 23 | lire(t[i]) |
| 24 | jusqua i = 0 ou t[i] ≥ t[i - 1] |
| 25 | fin_pour |
| 26 | fin |
| 27 | |
| 28 | procedure saisircible(@cible : entier) |
| 29 | debut |
| 30 | ecrire("Cible = ") |
| 31 | lire(cible) |
| 32 | fin |
| 33 | |
| 34 | fonction dichotomie(t : tab, n : entier, cible : entier) : entier |
| 35 | debut |
| 36 | // compléter le traitement demandé dans l’énoncé. |
| 37 | retourner -1 |
| 38 | fin |
| 39 | |
| 40 | procedure afficher(resultat : entier) |
| 41 | debut |
| 42 | ecrire_nl(resultat) |
| 43 | fin |
| 1 | algorithme recherche_dichotomique |
| 2 | debut |
| 3 | saisir(n) |
| 4 | remplir(t, n) |
| 5 | saisircible(cible) |
| 6 | indice ← dichotomie(t, n, cible) |
| 7 | afficher(indice) |
| 8 | fin |
| 9 | |
| 10 | procedure saisir(@n : entier) |
| 11 | debut |
| 12 | repeter |
| 13 | ecrire("N = ") |
| 14 | lire(n) |
| 15 | jusqua 1 ≤ n ≤ 100 |
| 16 | fin |
| 17 | |
| 18 | procedure remplir(@t : tab, n : entier) |
| 19 | debut |
| 20 | pour i de 0 à n - 1 faire |
| 21 | repeter |
| 22 | ecrire("t[" + convch(i) + "] = ") |
| 23 | lire(t[i]) |
| 24 | jusqua i = 0 ou t[i] ≥ t[i - 1] |
| 25 | fin_pour |
| 26 | fin |
| 27 | |
| 28 | procedure saisircible(@cible : entier) |
| 29 | debut |
| 30 | ecrire("Cible = ") |
| 31 | lire(cible) |
| 32 | fin |
| 33 | |
| 34 | fonction dichotomie(t : tab, n : entier, cible : entier) : entier |
| 35 | debut |
| 36 | gauche ← 0 |
| 37 | droite ← n - 1 |
| 38 | indice ← -1 |
| 39 | tant_que gauche ≤ droite et indice = -1 faire |
| 40 | milieu ← (gauche + droite) div 2 |
| 41 | si t[milieu] = cible alors |
| 42 | indice ← milieu |
| 43 | sinon |
| 44 | si t[milieu] < cible alors |
| 45 | gauche ← milieu + 1 |
| 46 | sinon |
| 47 | droite ← milieu - 1 |
| 48 | fin si |
| 49 | fin si |
| 50 | fin_tant_que |
| 51 | retourner indice |
| 52 | fin |
| 53 | |
| 54 | procedure afficher(resultat : entier) |
| 55 | debut |
| 56 | ecrire_nl(resultat) |
| 57 | fin |
Méthode
- Examiner le milieu de l’intervalle courant.
- Éliminer la moitié qui ne peut pas contenir la cible.
Comprendre la correction
Déroulement sur un exemple
- Pour T = [1, 3, 5, 8, 12] et Cible = 8, gauche = 0 et droite = 4. Le milieu est 2, où la valeur est 5.
- 8 est plus grand que 5 : on garde les indices 3 à 4. Leur milieu est 3 et t[3] = 8.
- La fonction retourne 3. Le tri permet d’écarter toute une moitié à chaque comparaison.
Erreurs à éviter
- Sur un tableau non trié, éliminer une moitié peut éliminer la cible elle-même.
- Déplacez une borne vers milieu + 1 ou milieu − 1. Garder milieu peut bloquer la recherche.