Recherche dichotomique

On fournit un tableau d'items.

Besoin : pour une valeur needle donnée, chercher l'indice de sa première occurrence dans le tableau, si elle s'y trouve, sinon -1.

Précondition : un critère d'ordre est défini et le tableau doit être trié dans l'ordre croissant.

Principe : Le tableau contient n = len(tableau) items. les indices vont de 0 à n - 1.

  • On initialise a à 0 et b à n - 1.
  • Nous faisons en sorte que si needle est dans le tableau, sa première occurrence est toujours entre a et b (ce qui est vrai avec les valeurs initiales de a et b)
  • Nous faisons aussi en sorte que l'écart b - a se réduise d'au moins 1 à chaque étape de sorte que l'écart b - a finit forcément par être nul.
  • Les deux éléments précédents font qu'à la fin, si needle est dans le tableau, sa première occurrence est forcément a – la valeur de a finale.

Voyons comment nous faisons évoluer a et b :

  • On lit la valeur du tableau à l'indice au milieu entre a et b : en i_m = (a + b)//2.
  • Si cette valeur >= needle cela signifie que la première occurrence de needle est forcément sur la gauche de i_m ou éventuellement en i_m. On peut donc continuer à chercher sur [a;i_m] et donc on décide que : b = i_m
    On sait que i_m < b, en choisissant b = i_m on réduit b d'au moins 1 et donc b - a aussi.
  • Sinon, cela signifie que valeur < needle et que needle est strictement à droite de i_m. On peut donc continuer à chercher dans [i_m + 1 ; b]]. On décide donc a = i_m + 1
    Si on se contentait de a = i_m, dans certains cas a ne changerait pas et donc b - a ne diminuerait plus, ce qui ferait une boucle infinie.

Exemple : 

tableau = [5, 7, 19, 21, 45, 45, 74]
n = len(tableau) # n = 7
needle = 45 # needle = aiguille, la valeur cherchée

# a et b délimitent la zone de recherche.
# On commence avec les bords du tableau : [0 ; 6]
a, b = 0, 6
i_m = (a + b) // 2 # i_m = 3

tableau[i_m] < needle # car tableau[i_m] = 21
# on peut continuer strictement sur la moitié droite
a = i_m + 14 # a passe à 4. La recherche continue sur [4 ; 6]

i_m = (a + b) // 2 # i_m = 5
tableau[i_m] >= needle # car tableau[i_m] = 45
# on peut continuer à gauche de 5
b = i_m # recherche continue sur [4;5]

i_m = (a + b) // 2 # i_m = 4
tableau[i_m] >= needle # car tableau[i_m] = 45
b = i_m # recherche continue sur [4;4]

# a == b pas besoin d'aller plus loin
# puisque tableau[a] == 45 == needle, la réponse est a = 4

La recherche de l'exemple s'est faite en 3 étapes ce qui correspond au fait que $7 < 2^3$. Si le tableau contenait $n = 1\,000\,000 < 2^{20}$ items, 20 étapes suffiraient.

À faire
Implémenter en Python un algorithme de recherche par dichotomie.