informatique (tronc commun des prépas scientifiques) · Chapitre 10 · Application directe du cours
Le partitionnement de dichotomie
Prouver et analyser : la boîte à outils formalisée · niveau 1 (application)
Énoncé
Construire le partitionnement complet du domaine d'entrée de la recherche dichotomique.
Corrigé
Le partitionnement s'établit sur trois axes :
- Présence de l'élément :
- Élément présent.
- Élément absent.
- Cheminement dans le tableau (structure) :
- Trouvé dès le premier milieu (0 division).
- Recherche orientée vers la gauche.
- Recherche orientée vers la droite.
- Absent inférieur à tous les éléments.
- Absent supérieur à tous les éléments.
- Absent intercalé entre deux valeurs.
- Taille du tableau (limites) :
- Tableau vide.
- Tableau à 1 élément (présent ou absent).
- Tableau général.
- Tableau contenant des doublons.