Admin CliCours
Exercice langage C corrigé recherche dichotomique, tutoriel & guide de travaux pratiques en pdf.
RECHERCHE DICHOTOMIQUE DANS UN TABLEAU ORDONNE.
On considère un tableau U de I nombres entiers deux à deux distincts, rangés par ordre croissant, et un nombre Y. Ecrivez un programme qui détermine l’indice exprimant soit le rang de Y dans U soit, si Y ne figure pas dans U, le rang de l’emplacement dans lequel il faudrait ranger Y pour l’insérer dans le tableau, en conservant trié ce dernier.
Principe : considérer deux indices v et w tels que le sous-tableau [ ? … ? ] soit seul susceptible de contenir Y (initialement, v = 0 et w = I-1). En comparant Y et l’élément du milieu, déterminer celle des deux moitiés du sous-tableau qui est susceptible de contenir Y. Recommencer cette opération jusqu’à déterminer une unique position du tableau.
Estimez le nombre moyen d’opérations faites par ce programme et par celui du n° 4. Estimez le nombre moyen d’opérations faites par l’une et l’autre méthode, lorsque la recherche d’un élément qui ne figure pas dans le tableau doit être suivie de son insertion.
La correction exercice langage C (voir page 2 en bas)
J’ai besoin d’aide sur un exercice
Ecrire un algorithme permettant de faire la recherche dichotomique de deux entiers distincts
dans un tableau d’entiers triés. NB : Vous regarderez tous les cas possibles d’appartenance de
ces deux entiers dans le tableau.