Dichotomie, voisins et gloutons

Le chapitre précédent a démontré la correction de boucles ; celui-ci en tire parti pour trois algorithmes qui, chacun, illustrent une idée différente. La recherche dichotomique montre ce qu'on gagne à exploiter une structure — ici, le fait que le tableau soit trié. Les $k$ plus proches voisins montrent qu'un algorithme peut prédire. Les algorithmes gloutons montrent qu'une stratégie simple peut être excellente… ou fausse, et qu'il faut savoir dire laquelle.

8.1 La recherche dichotomique

8.1.1 Diviser l'intervalle par deux

Chercher un mot dans un dictionnaire papier, personne ne le fait en partant de la première page. On ouvre au milieu, on regarde si le mot cherché est avant ou après, et on recommence sur la moitié retenue. Chaque coup d'œil élimine la moitié de ce qui reste.

def dichotomie(t, v):
    """Indice d'une occurrence de v dans le tableau TRIÉ t, ou -1 si absente.

    Précondition  : t est trié par ordre croissant.
    Postcondition : si le résultat r vaut -1, v ne figure pas dans t ;
                    sinon t[r] == v.
    """
    gauche = 0
    droite = len(t) - 1
    while gauche <= droite:
        # invariant : si v figure dans t, alors son indice est dans
        #             l'intervalle [gauche, droite]
        milieu = (gauche + droite) // 2
        if t[milieu] == v:
            return milieu
        elif t[milieu] < v:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Figure : Chaque comparaison élimine la moitié des candidats. Treize cases, puis six, puis deux : trente comparaisons suffisent pour un milliard d'éléments.

8.1.2 La terminaison, par un variant