L'essentiel à connaître
Pour chercher $x$ dans un tableau trié, la dichotomie compare $x$ à la case du milieu et jette la moitié où il ne peut pas être : sur un milliard de valeurs, 30 tours de boucle suffisent au pire. Sans tri, il reste la recherche séquentielle : comparer $x$ à chaque case, soit $n$ comparaisons au pire pour $n$ éléments. Ce coût en temps, appelé complexité, est en $O(n)$, contre $O(\log n)$ pour la dichotomie.
def dichotomie(t, x):
g, d = 0, len(t) - 1
while g <= d:
m = (g + d) // 2
if t[m] == x:
return m
elif t[m] < x:
g = m + 1
else:
d = m - 1
return -1À chaque tour, la zone de recherche, de g à d, perd la case du milieu et garde au plus la moitié de ses cases : la boucle finit forcément. Au pire, elle fait $\lfloor \log_2 n \rfloor + 1$ tours ($\lfloor \cdot \rfloor$ : partie entière), et doubler $n$ n'ajoute qu'un tour.
Cette version itérative n'ajoute que trois variables : $O(1)$ en mémoire. Une version récursive empile un appel par tour sur la pile d'appels (la mémoire des appels en cours) : $O(\log n)$. En Python, une tranche t[:m] est une copie, en $O(k)$ pour $k$ éléments, et x in t sur une liste est une recherche séquentielle (wiki Python).
Définition : $f(n) = O(h(n))$ s'il existe $c > 0$ tel que $f(n) \le c\,h(n)$ pour tout $n$ assez grand : un majorant, pas forcément le plus précis. $\Theta(h(n))$ encadre $f$ entre deux multiples de $h$.
À retenir : De la croissance la plus lente à la plus rapide : $\log n$, $n$, $n\log n$, $n^2$, $2^n$. Un bon tri (tri fusion) coûte $O(n\log n)$ : il ne vaut le coup que pour de nombreuses recherches.
Quiz : teste tes connaissances
Les questions montent en difficulté : les trois dernières sont les plus piégeuses. Pour un coût, donne le $O$ le plus précis.
Question 1 : Que faut-il pour lancer une recherche dichotomique sur un tableau ?
Réponse : C. Comparer $x$ au milieu ne dit où chercher que si les valeurs sont rangées dans l'ordre. Les doublons ne gênent pas : la fonction renvoie l'une des positions de $x$.
Question 2 : En Python, que coûte au pire le test x in t quand t est une liste de $n$ éléments ?
Réponse : A. Sur une liste, in compare $x$ aux éléments un par un : jusqu'à $n$ comparaisons. Le piège $O(1)$ vaut pour les ensembles et les dictionnaires, en moyenne (wiki Python).
Question 3 : Le tableau est trié dans l'ordre croissant et t[m] dépasse $x$. Où continue la recherche ?
Réponse : D. Tout ce qui suit t[m] est encore plus grand que $x$ : on ramène la borne droite juste avant le milieu. Le piège B part du bon côté, mais c'est d qui doit bouger, pas g.
Question 4 : Combien de tours de boucle fait dichotomie pour trouver 21 dans [3, 8, 12, 17, 21, 30, 42] ?
Réponse : B. Tour 1 : t[3] vaut 17, trop petit, donc $g = 4$. Tour 2 : t[5] vaut 30, trop grand, donc $d = 4$. Tour 3 : t[4] vaut 21. Le piège D compte la recherche séquentielle, case par case.
Question 5 : Quand $n$ devient grand, dans quel ordre ces fonctions croissent-elles, de la plus lente à la plus rapide ?
Réponse : A. $n\log n$ dépasse $n$ mais reste bien en dessous de $n \times n$. Le piège D vient des petites valeurs : $2^3 = 8 < 3^2 = 9$, mais dès $n = 5$, $2^n$ dépasse $n^2$ pour de bon.
Question 6 : Au plus, combien de tours de boucle fait dichotomie dans un tableau trié de $10^6$ éléments ?
Réponse : D. $2^{19} = 524\,288 \le 10^6 < 2^{20} = 1\,048\,576$, donc $\lfloor \log_2 10^6 \rfloor + 1 = 20$. Le piège A vient du logarithme décimal : la dichotomie divise par 2, pas par 10.
Question 7 : Ton tableau trié passe de $n$ à $2n$ éléments. Que devient le nombre maximal de tours de la dichotomie ?
Réponse : A. $\lfloor \log_2 (2n) \rfloor + 1 = \lfloor \log_2 n \rfloor + 2$ : un tour de plus. Le piège B décrit la recherche séquentielle, dont le travail double avec $n$.
Question 8 : Tu cherches une seule fois une valeur dans une liste non triée de $n$ éléments. Quelle méthode coûte le moins au pire ?
Réponse : C. Le tri seul coûte $O(n\log n)$, plus que tout le parcours en $O(n)$. La méthode B échoue : sans tri, jeter une moitié peut jeter $x$.
Question 9 : Tu fais maintenant $n$ recherches dans cette liste : un tri en $O(n\log n)$, puis $n$ dichotomies. Quel coût total ?
Réponse : B. Le tri coûte $O(n\log n)$, et les $n$ dichotomies, à $O(\log n)$ chacune, aussi : $O(n\log n)$ en tout. Le piège A est le coût de $n$ recherches séquentielles, sans tri.
Question 10 : En Python, une dichotomie récursive passe g et d en paramètres, sans copier le tableau. Quelle mémoire supplémentaire utilise-t-elle au pire ?
Réponse : D. Chaque appel attend le suivant et garde sa place sur la pile : environ $\log_2 n$ appels empilés. Le piège A vaut pour la version itérative.
Question 11 : Dans dichotomie, on remplace d = m - 1 par d = m, puis on cherche 0 dans [1, 3]. Que se passe-t-il ?
Réponse : B. Tour 1 : t[0] vaut 1, trop grand, donc $d = m = 0$. Ensuite $g = d = m = 0$ à chaque tour : la zone ne rétrécit plus. Le piège A oublie que d = m laisse la case du milieu dans la zone.
Question 12 : Un camarade écrit : « la recherche séquentielle est en $O(n^2)$ ». Qu'en penses-tu ?
Réponse : C. Au pire, $n$ comparaisons, et $n \le n^2$ : elle est donc aussi en $O(n^2)$, même si c'est grossier. Le piège A confond $O$, qui majore, avec $\Theta$, qui encadre : elle est en $\Theta(n)$.
Question 13 : On remplace while g <= d par while g < d, puis on cherche 9 dans [2, 5, 9]. Que se passe-t-il ?
Réponse : D. Tour 1 : t[1] vaut 5, trop petit, donc $g = 2$. Reste la case de 9, mais $2 < 2$ est faux : la boucle s'arrête sans la tester. Le piège A suppose cette dernière case testée, comme avec <=.
Question 14 : En Python, une dichotomie récursive se rappelle sur une copie de la bonne moitié, t[:m] ou t[m + 1:]. Quel est son coût en temps au pire ?
Réponse : A. Chaque tranche est une copie en $O(k)$ : $n/2 + n/4 + \dots < n$ éléments copiés, donc $O(n)$, comme une recherche séquentielle. Le piège B compte les tours, pas le prix de chaque tour.
Question 15 : Au plus, combien de tours de boucle fait dichotomie dans un tableau trié de 1 024 éléments ?
Réponse : C. Au pire, la zone passe par $2^{10}, 2^9, \dots, 2^1, 2^0$ cases, une taille par tour : 11 tours, soit $\lfloor \log_2 1024 \rfloor + 1$. Le piège A, c'est $\log_2 1024 = 10$ : il oublie le dernier tour, sur la case restante.
Sources
Wiki de Python, page « TimeComplexity » : coût des opérations de base en Python. wiki.python.org/moin/TimeComplexity