Algorithmes dichotomiques

Cours · informatique (tronc commun des prépas scientifiques), chapitre 5 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun

La recherche dichotomique : dans un tableau trié, on élimine à chaque étape la moitié des cases restantes.

5.1 Introduction et motivation

Pour trouver un mot dans le dictionnaire — le vrai, celui en papier — personne ne lit les pages une à une : on ouvre au milieu, on compare, et l'on sait aussitôt dans quelle moitié continuer. Chaque regard divise par deux l'espace de recherche : trente regards suffisent pour un milliard de pages. Ce principe, la dichotomie (littéralement : couper en deux), est la première grande idée algorithmique du cours, et la plus spectaculaire : elle fait passer la recherche du coût linéaire $O (n)$ du chapitre 2 au coût logarithmique $O (lo g n)$ — à condition, et c'est tout le prix à payer, que le tableau soit trié.

Mais la dichotomie est aussi l'algorithme le plus traître du semestre : deux indices, des bornes incluses ou exclues, un milieu à arrondir — « bien que l'idée de base de la recherche dichotomique soit relativement simple, les détails peuvent être étonnamment retors », écrivait Donald Knuth. C'est donc ici que les outils de validation du chapitre 1 — variant, invariant, jeux de tests — cessent d'être des exercices d'école : sans eux, on n'écrit pas une dichotomie juste. Le chapitre culmine avec une seconde dichotomie déguisée, l'exponentiation rapide, qui calcule $x^{n}$ en $O (lo g n)$ multiplications.

5.2 Le coût logarithmique

Définition 5.1Logarithme binaire

Le logarithme binaire de $n$ , noté $lo g_{2} n$ , est l'exposant tel que $2^{l o g_{2} n} = n$ . Pour l'algorithmique, une seule propriété compte : $⌊ lo g_{2} n ⌋ + 1$ est le nombre de divisions par 2 (avec arrondi) nécessaires pour passer de $n$ à $1$ — ou, ce qui revient au même, le nombre de chiffres de $n$ en binaire.

Complexité : L'échelle, complétée

Un algorithme est de complexité logarithmique si son coût dans le cas le pire est $O (lo g n)$ . L'échelle du chapitre 2 s'enrichit d'une ligne qui change tout :

$n$	$1 0^{3}$	$1 0^{6}$	$1 0^{9}$
$O (lo g n)$	$\sim 10$ opérations	$\sim 20$	$\sim 30$
$O (n)$	$1 0^{3}$	$1 0^{6}$	$1 0^{9}$
$O (n^{2})$	$1 0^{6}$	$1 0^{12}$	$1 0^{18}$

Trente opérations pour chercher dans un milliard d'éléments : le logarithme croît si lentement qu'à l'échelle humaine, il est presque constant. Doubler $n$ n'ajoute qu'une seule opération.

5.3 La recherche dichotomique

5.3.1 L'algorithme

Définition 5.2Recherche dichotomique

Dans un tableau trié $t$ , on cherche $v$ en maintenant une fenêtre $t [g .. d]$ (bornes incluses) où $v$ peut encore se trouver. À chaque étape, on compare $v$ à l'élément du milieu et l'on jette la moitié inutile :


def dichotomie(v, t: list):
    """Renvoie un indice i tel que t[i] == v, ou None si v est absent.
    Précondition : t est trié en ordre croissant."""
    g, d = 0, len(t) - 1
    while g <= d:
        # Invariant : si v est dans t, alors v est dans t[g..d]
        m = (g + d) // 2
        if t[m] == v:
            return m
        elif t[m] < v:
            g = m + 1          # v, s'il existe, est strictement à droite de m
        else:
            d = m - 1          # v, s'il existe, est strictement à gauche de m
    return None

Exercices du chapitre

Zéro d'une fonction continue corrigé
La première occurrence corrigé
Puissances de matrices et Fibonacci corrigé
L'exponentiation modulaire corrigé
Le bogue du milieu, quarante ans dans les bibliothèques corrigé
Combien de comparaisons, au mieux ? corrigé

La suite du cours · Tous les exercices du chapitre