Exemple:
Recherche de la valeur 89, dans le tableau:
tab[] = 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,INF,INF,INF,INF,INF,INF,...
phase 1: recherche de l'indice d'un majorant de 89
tab[1]=1
tab[2]=1
tab[4]=3
tab[8]=21
tab[16]=987 <--- majorant #16
phase 2: recherche dichotomique de 89 dans les elements du tableau entre #8 (plus grand minorant) et #16 (majorant)
tab[(8+16)/2] = tab[12] = 144 => trop haut => Recherche dans la partie gauche [#8,#11]
tab[(8+11)/2] = tab[9] = 34 => trop bas => Recherche dans la partie droite [#10,#11]
tab[(10+11)/2] = tab[10] = 55 => trop bas => Recherche dans la partie droite [#11,#11]
tab[(11+11)/2] = tab[11] = 89 => trouvé !!
Partager