É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.