On clarifie ici ce que l'on peut appeler élément milieu d'une liste.

Dans tous les cas, dans une liste de n éléments, on peut facilement définir un élément tel que les deux sous-listes à gauche et à droite de cet élément contiennent chacune au plus \( \lfloor \frac{n}{2} \rfloor \) éléments. Il est facile de s'en convaincre avec quelques exemples. On explicite ici une formule donnant l'indice d'un tel élément.

On dispose d'une liste, ou plutôt d'une sous-liste de liste :
[ L[a], L[a+1], L[a+2], ..., L[b] ], contenant \( n = b-a+1 \) éléments.

On nomme élément milieu de la liste, l'élément d'indice (a+b)//2 -- où (notation python) (a+b)//2 est le quotient de la division euclidienne de a+b par 2.

On note q ce quotient (c'est à dire \( q = \lfloor \frac{a+b}{2} \rfloor \) ).

• La sous-liste gauche est [L[a], L[a+1], ..., L[q-1] ]. Elle contient (q-1)-a+1 = q-a éléments.
• La sous-liste droite est [L[q+1], L[q+2], ..., L[b] ]. Elle contient b - (q+1) +1 = b-q éléments.

Explicitons le nombre d'éléments de chacune de ces sous-listes.

• Cas 1. a+b = 2q. Dans ce cas, b-q = (2q-a)-q = q-a. Les deux sous-listes contiennent le même nombre d'éléments.
  Ce nombre d'éléments est bien sûr le quotient de la division entière par 2 du nombre d'éléments initial dans la sous-liste : b-a+1 = 2(q-a) +1, soit \( q-a = \lfloor \frac{n}{2} \rfloor \).
• Cas 2. a+b = 2q+1. Dans ce cas, b-q = (2q+1-a)-q = q-a+1. L'une des deux sous-listes contient un élément de plus que l'autre.
  On a b-a+1 = 2(q-a+1). L'une des sous-listes contient donc \( \lfloor \frac{n}{2} \rfloor \) éléments, et l'autre en contient un de moins.

def recherche(element, liste):
	
	def dichotomie(mini, maxi):
		if mini > maxi : return -1
		m = (mini+maxi)//2
		if liste[m] == element : return m
		elif liste[m] < element : return dichotomie(m+1, maxi)
		else : return dichotomie(mini, m-1)
	
	return dichotomie(0, len(liste)-1)


L = [2,4,9,15,41]
print( recherche(16, L) )
print( recherche(15, L) )

La liste L est [l₀, l₁, ..., l₇ ].

Supposons que l'on cherche l'élément maximal de L avec l₀ ≤ l₁ ≤ ... ≤ l₆ < l₇. On recherche donc l'élément x = l₇.

Initialisation : debut=0, fin=7.

1. Étape 1. debut = 0, fin = 7. milieu = 3, L[3] < x.
2. Étape 2. debut = 4, fin = 7. milieu = 5, L[5] < x.
3. Étape 3. debut = 6, fin = 7. milieu = 6, L[6] < x.
4. Étape 4. debut = 7, fin = 7. milieu = 7, L[7] == x.

Il a donc fallu 4 étapes pour trouver une occurrence de x. Or blog(8)+1 = blog(2³)+1 = 3+1 = 4.

Remarque. Si on cherche un élément x > L[7], la boucle de l'étape 4 ne permet pas de conclure, mais on ne rentrera toutefois pas une fois de plus dans la boucle puisqu'on aura debut > fin (condition du while non respectée). On aura donc le même nombre d'étapes si l'on appelle, comme suggéré dans l'énoncé, 'étape' une exécution du contenu de la boucle.

Supposons comme précédemment que la liste contient des nombres distincts et que l'on cherche l'élément x de valeur maximale (donc d'indice 2^k-1 dans la liste).

1. Étape 1. debut = 0, fin = 2^k-1, milieu = 2^k-1-1, L[2^k-1-1] < x.
2. Étape 2. debut = 2^k-1, fin = 2^k-1, milieu=2^k-2+2^k-1-1, L[2^k-2+2^k-1-1] < x.
3. Étape 3. debut = 2^k-2+2^k-1, fin = 2^k-1, milieu = 2^k-3+2^k-2+2^k-1-1, L[2^k-3+2^k-2+2^k-1-1] < x.
4. Étape 4. debut = 2^k-3+2^k-2+2^k-1, fin = 2^k-1, milieu = 2^k-4+2^k-3+2^k-2+2^k-1-1, L[2^k-4+2^k-3+2^k-2+2^k-1-1] < x.
5. ...
6. Etape j. \[ \text{debut} = \sum_{i=1}^{j-1} 2^{k-i}\] soit (progression géométrique... calculer 2*debut-debut=debut) \[ \text{debut} = 2^{k}-2^{k-(j-1)}\] fin est toujours égal à 2^k-1 et \[ \text{milieu}= \sum_{i=1}^{j} 2^{k-i}-1\]
7. ...
8. Etape k+1. \[ \text{debut} = \sum_{i=1}^{k+1-1} 2^{k-i}\] soit \[ \text{debut} = 2^{k}-1\] fin=2^k-1 et cette étape permet de conclure.

On a donc eu besoin de k+1 = blog( 2^k)+1 = blog(n)+1 étapes.

On remarquera qu'une étape nécessite en général un test == et un test <. Ici la dernière étape ne nécessitait qu'un seul des deux tests, mais les deux peuvent avoir lieu (cas de la recherche d'une valeur strictement plus grande que le maximum de la liste). On peut donc avoir besoin de 2(blog(n)+1) tests (== ou <) dans la recherche d'un élément dans la liste.

Pour établir que blog(n)+1 étapes suffisent, on va utiliser le fait que partant d'une liste de longueur m, on aboutit à une liste de longueur au plus m//2.

Soit L une liste de longueur n.

1. Avec l'étape 1, on réduit la recherche à une liste de taille au plus n//2.
2. Avec l'étape 2, on réduit la recherche à une liste de taille au plus n//(2²).
3. Avec l'étape 3, on réduit la recherche à une liste de taille au plus n//(2³).
4. ...
5. A l'étape j, on réduit la recherche à une liste de taille au plus n//(2^j).
6. ...
7. A l'étape blog(n), on réduit la recherche à une liste de taille au plus n//(2^blog(n)).

Par définition de blog(n), on a n//(2^blog(n)) ≤1. Il ne reste donc qu'au plus un élément à tester après cette étape blog(n). On aura donc terminé à l'étape suivante.

blog(n)+1 étapes suffisent donc toujours.

Calcul direct des deux nombres d'étapes

Dans les deux cas, il s'agit de calculer blog(n)+1. Rappelons que blog(n) se calcule facilement par un petit programme python :

def blog(x) :
    n = 0
    while x>1 :
        x/=2
        n+=1
    return n
    
    
print('Pop française : ', blog(65*10**6)+1 )
print('Pop mondiale : ', blog(7*10**9)+1)

ce qui donne :

Pop française :  27
Pop mondiale :  34

Calcul du second nombre d'étapes à partir du premier.

\( \frac{7 \times 10^9}{65 \times 10^6} \approx 107,69 \)

La population mondiale est plus de 107 fois la population française.

Comme \( \log_2(ab) = \log_2(a) + \log_2(b) \), on peut écrire : \(\log_2( \text{pop mondiale} ) \approx \log_2( 107,69 ) + \log_2( \text{pop francaise})\)

Comme \( \log_2( 107.69) \approx 6.75 \), on comprend maintenant pourquoi le nombre d'étapes augmente aussi peu entre une recherche dans un annuaire de 65 millions d'entrées et une recherche dans un annuaire de 7 milliards d'entrées.