# recherche dichotomique

def recherche_dichotomique(t, v):
    """renvoie une position de v dans le tableau t,
    supposé trié, et None si v ne s'y trouve pas"""
    g = 0
    d = len(t) - 1
    while g <= d:
        # invariant : 0 <= g et d < len(t)
        # invariant : v ne peut se trouver que dans t[g..d]
        m = (g + d) // 2
        if t[m] < v:
            g = m + 1
        elif t[m] > v:
            d = m - 1
        else:
            return m
    # la valeur ne se trouve pas dans le tableau
    return None