Chercher dans l'infini — la recherche par doublement

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 5 — Algorithmes dichotomiques

Énoncé

Soit une suite infinie strictement croissante $u_{0} < u_{1} < \dots$ définie par une fonction u(i). On cherche l'indice $i$ d'une valeur $v$ . Proposer un algorithme de complexité $O (lo g i^{*})$ (où $i^{*}$ est la position attendue) sans connaître à l'avance de borne supérieure sur l'indice.

Corrigé

On procède en deux phases :

Phase de doublement : On cherche une borne supérieure en évaluant la fonction aux indices puissances de 2 ( $1, 2, 4, 8, \dots$ ) jusqu'à trouver un indice $d$ tel que $u (d) \geq v$ . Cette étape prend $O (lo g i^{*})$ étapes.
Phase de dichotomie : On sait alors que $v$ se trouve dans l'intervalle $[g, d]$ avec $g = d //2$ . On effectue une recherche dichotomique classique sur cet intervalle de largeur $d - g = d /2 \leq i^{*}$ , ce qui prend également $O (lo g i^{*})$ opérations.

def recherche_infinie(u, v):
    if u(0) == v:
        return 0
    if u(0) > v:
        return None
    
    # Phase 1 : Trouver la borne supérieure
    d = 1
    while u(d) < v:
        d = d * 2
    
    # Phase 2 : Recherche dichotomique sur la fenêtre trouvée [d // 2, d]
    g = d // 2
    while g <= d:
        m = (g + d) // 2
        val_m = u(m)
        if val_m == v:
            return m
        elif val_m < v:
            g = m + 1
        else:
            d = m - 1
    return None

La complexité globale est bien en $O (lo g i^{*})$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.