Je teste mes connaissances :
Recherche Dichotomique
Recherche Dichotomique
Question n°1
Soit une fonction recherche_dicho(t,n,x)qui effectue une recherche dichotomique de x(entier) parmi les n éléments d'unTableau trié et qui renvoie l'indice de x dans le tableau.
Exécuter "à la main" votre fonction sur les données suivantes :
n=10,t=[1,7,8,9,12,15,15,22,30,31]et x=22
On définit 2 indices haut et bas du tableau avec bas=0 et haut=9
On commence par déterminer l'indice de milieu du tableau soit ind = (bas+haut)/2 = (0+9)/2 soit 4 (valeur entière)
Cela correspond à la valeur 12.
On compare x soit 22 à cette valeur 12. Elle se trouve au-delà de l'indice 4.
On recherche donc la valeur entre les indices bas=5 et haut=9.
On détermine l'indice de milieu du sous-tableau soit ind = (haut-bas)/2 = (5+9)/2 soit 7 (valeur entière)
Cela correspond à la valeur 22 ... la valeur que nous recherchons.
La fonction renvoie donc la position d'indice 7 pour notre valeur.