Écrire premier vrai(predicat, n)

def premier_vrai(predicat, n):
    """Plus petit i de [0, n[ tel que predicat(i), ou n si aucun.

    Precondition : predicat est CROISSANT (faux, puis vrai).
    """
    gauche, droite = 0, n
    while gauche < droite:
        milieu = (gauche + droite) // 2
        if predicat(milieu):
            droite = milieu
        else:
            gauche = milieu + 1
    return gauche

assert premier_vrai(lambda i: i >= 7, 20) == 7
assert premier_vrai(lambda i: False, 20) == 20    # aucun : on renvoie n
assert premier_vrai(lambda i: True, 20) == 0

C'est la dichotomie débarrassée du tableau. Il n'y a plus de t, plus de valeur cherchée : seulement une propriété qui bascule une fois. Le tableau trié du cours n'était qu'un cas particulier de cette situation — « $t[i]\ge v$ » est précisément un prédicat croissant.

La mesure.

compteur = {"n": 0}

def cher(i):
    compteur["n"] += 1
    return i * i >= 1000000

assert premier_vrai(cher, 10**6) == 1000
assert compteur["n"] == 20

Vingt appels pour un million de candidats — et $20=(10^6).\text{bit\_length}()$, une fois de plus. Le prédicat est ici bon marché, mais l'intérêt de la méthode apparaît quand il est coûteux : chercher la plus grande charge qu'un serveur supporte, ou le premier jour où une population dépasse un seuil, en vingt essais au lieu d'un million.

La précondition est la seule chose à surveiller. Si le prédicat n'est pas croissant — vrai, puis faux, puis vrai — la fonction renvoie un point de bascule, pas le premier, et sans prévenir. C'est le même défaut, exactement, que la dichotomie sur un tableau non trié.