Algorithmes de recherches

1. Recherche de 23.

3 comparaisons, contre 6 pour une recherche sequentielle.

2. Recherche de 4.

3. Au plus \(\lfloor\log_2 10\rfloor + 1 = 4\) comparaisons. L'arbre de decision de la dichotomie sur 10 elements a une hauteur de 3, donc au plus 4 noeuds sur un chemin.

4. Une seule comparaison : \(t[4] = 16\), l'element median. Deux comparaisons : \(t[1] = 5\) et \(t[7] = 56\), les medians des deux moities. Trois : \(t[0], t[2], t[5], t[8]\). Quatre : \(t[3], t[6], t[9]\). On reconnait les niveaux de l'arbre de decision.

import random
from math import log2, floor

def dichotomie(t, v):
    """Indice de v dans la liste triee t, ou -1."""
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == v:
            return m
        if t[m] < v:
            g = m + 1
        else:
            d = m - 1
    return -1

def dichotomie_comptee(t, v):
    g, d, n = 0, len(t) - 1, 0
    while g <= d:
        m = (g + d) // 2
        n += 1
        if t[m] == v:
            return m, n
        if t[m] < v:
            g = m + 1
        else:
            d = m - 1
    return -1, n

# 2. validation exhaustive
for _ in range(500):
    n = random.randint(0, 30)
    t = sorted(random.sample(range(100), n))
    for v in range(100):
        i = dichotomie(t, v)
        if v in t:
            assert i >= 0 and t[i] == v
        else:
            assert i == -1
print("dichotomie validee")

# 3. borne sur le nombre de comparaisons
for n in (10, 100, 1000, 10**5):
    t = list(range(0, 2*n, 2))
    pire = max(dichotomie_comptee(t, v)[1] for v in range(0, 2*n))
    print(f"n = {n:>7} : pire cas = {pire}, borne = {floor(log2(n)) + 1}")

n =      10 : pire cas = 4, borne = 4
n =     100 : pire cas = 7, borne = 7
n =    1000 : pire cas = 10, borne = 10
n =  100000 : pire cas = 17, borne = 17

4. Sur une liste non triee, l'invariant « si \(v\) est present, il est dans \(t[g..d]\) » est faux : rien ne garantit que les elements a gauche de \(m\) soient inferieurs a \(t[m]\).

t = [5, 1, 9, 3, 7]        # non triee
print(dichotomie(t, 1))    # -1 : pourtant 1 est present a l'indice 1 !
# etape 1 : m = 2, t[2] = 9 > 1 donc d = 1
# etape 2 : m = 0, t[0] = 5 > 1 donc d = -1
# g > d : la fonction conclut a tort que 1 est absent

L'algorithme ne detecte pas l'erreur : il renvoie une reponse fausse silencieusement. C'est pourquoi la precondition doit etre documentee, et eventuellement verifiee par un assert en phase de mise au point (au prix d'un cout \(\Theta(n)\), qui annule l'interet de la dichotomie — donc a retirer en production).

import bisect, random

def premiere_occurrence(t, v):
    """Plus petit indice i tel que t[i] == v, ou -1. Theta(log n)."""
    g, d, res = 0, len(t) - 1, -1
    while g <= d:
        m = (g + d) // 2
        if t[m] == v:
            res = m                # candidat trouve, mais on continue A GAUCHE
            d = m - 1
        elif t[m] < v:
            g = m + 1
        else:
            d = m - 1
    return res

def derniere_occurrence(t, v):
    """Plus grand indice i tel que t[i] == v, ou -1."""
    g, d, res = 0, len(t) - 1, -1
    while g <= d:
        m = (g + d) // 2
        if t[m] == v:
            res = m
            g = m + 1              # on continue A DROITE
        elif t[m] < v:
            g = m + 1
        else:
            d = m - 1
    return res

def compte(t, v):
    """Nombre d'occurrences de v. Theta(log n)."""
    p = premiere_occurrence(t, v)
    if p == -1:
        return 0
    return derniere_occurrence(t, v) - p + 1

def position_insertion(t, v):
    """Indice ou inserer v en preservant le tri (a gauche des egaux)."""
    g, d = 0, len(t)
    while g < d:
        m = (g + d) // 2
        if t[m] < v:
            g = m + 1
        else:
            d = m
    return g

t = [1, 3, 3, 3, 3, 7, 9, 9]
assert premiere_occurrence(t, 3) == 1
assert derniere_occurrence(t, 3) == 4
assert compte(t, 3) == 4 and compte(t, 5) == 0
assert position_insertion(t, 5) == 5

for _ in range(500):
    u = sorted(random.choices(range(10), k=random.randint(0, 25)))
    for v in range(11):
        assert compte(u, v) == u.count(v)
        assert position_insertion(u, v) == bisect.bisect_left(u, v)
print("recherche de bornes validee")

L'astuce commune est de ne pas s'arreter a la premiere occurrence trouvee : on memorise le candidat dans res et l'on poursuit la dichotomie du cote voulu. Le nombre de tours reste \(\Theta(\log n)\).

4. Le module standard offre :

• bisect.bisect_left(t, v) : premier indice \(i\) avec \(t[i] \ge v\) — identique a position_insertion ;
• bisect.bisect_right(t, v) : premier indice avec \(t[i] > v\) ;
• bisect.insort(t, v) : insere en preservant le tri (\(\Theta(\log n)\) pour la recherche, mais \(\Theta(n)\) pour le decalage).

n = bisect.bisect_right(t, 3) - bisect.bisect_left(t, 3)     # 4 occurrences

def racine_entiere(n):
    """Plus grand k tel que k*k <= n, pour n >= 0. Theta(log n), exact."""
    if n < 2:
        return n
    g, d = 0, n
    while g < d:
        m = (g + d + 1) // 2         # arrondi SUPERIEUR : evite la boucle infinie
        if m * m <= n:
            g = m
        else:
            d = m - 1
    return g

def racine_pieme(n, p):
    """Plus grand k tel que k**p <= n, pour n >= 0 et p >= 1."""
    if n < 2 or p == 1:
        return n
    g, d = 0, n
    while g < d:
        m = (g + d + 1) // 2
        if m ** p <= n:
            g = m
        else:
            d = m - 1
    return g

def log_entier(n, b):
    """Plus grand k tel que b**k <= n. Precondition : n >= 1, b >= 2."""
    k, p = 0, 1
    while p * b <= n:
        p *= b; k += 1
    return k

for n in range(0, 20000):
    r = racine_entiere(n)
    assert r*r <= n < (r+1)*(r+1)
assert racine_pieme(1000, 3) == 10
assert racine_pieme(999, 3) == 9
assert log_entier(1023, 2) == 9 and log_entier(1024, 2) == 10
print("racines entieres validees")

4. int(n ** 0.5) passe par un flottant sur 53 bits de mantisse. Pour \(n\) grand, l'arrondi peut donner un resultat faux :

n = 10**18
print(int(n ** 0.5))            # 1000000000
n = (10**9 + 1)**2 - 1
print(int(n ** 0.5))            # 1000000001  : FAUX, la vraie reponse est 1000000000
print(racine_entiere(n))        # 1000000000  : correct

import math
print(math.isqrt(n))            # 1000000000  : la fonction exacte de la bibliotheque

La dichotomie ne manipule que des entiers : elle est exacte quelle que soit la taille de \(n\). C'est la raison d'etre de math.isqrt, ajoutee a Python 3.8.

import random

def indice_rotation(t):
    """Indice du minimum d'une liste triee puis tournee (sans doublon). Theta(log n)."""
    g, d = 0, len(t) - 1
    while g < d:
        m = (g + d) // 2
        if t[m] > t[d]:
            g = m + 1          # le minimum est strictement a droite de m
        else:
            d = m              # m peut etre le minimum
    return g

def recherche_tournee(t, v):
    """Indice de v dans une liste triee tournee, ou -1. Theta(log n), un seul parcours."""
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == v:
            return m
        if t[g] <= t[m]:                       # la moitie GAUCHE est triee
            if t[g] <= v < t[m]:
                d = m - 1
            else:
                g = m + 1
        else:                                  # la moitie DROITE est triee
            if t[m] < v <= t[d]:
                g = m + 1
            else:
                d = m - 1
    return -1

for _ in range(1000):
    n = random.randint(1, 20)
    base = sorted(random.sample(range(100), n))
    k = random.randrange(n)
    t = base[k:] + base[:k]
    assert t[indice_rotation(t)] == base[0]
    for v in range(100):
        i = recherche_tournee(t, v)
        assert (i == -1) if v not in t else (t[i] == v)
print("recherche dans une liste tournee validee")

3. Justification. Bien que la liste ne soit pas globalement triee, elle est la concatenation de deux parties triees. En comparant \(t[g]\) et \(t[m]\), on determine laquelle des deux moities \([g,m]\) et \([m,d]\) est entierement triee :

• si \(t[g] \le t[m]\), la moitie gauche ne contient pas le point de rupture, donc elle est triee ; on peut y decider par un simple encadrement si \(v\) s'y trouve ;
• sinon, c'est la moitie droite qui est triee.

Dans les deux cas on elimine une moitie : l'invariant « si \(v\) est present, il est dans \(t[g..d]\) » est preserve, et le variant \(d-g+1\) decroit strictement. La complexite reste \(\Theta(\log n)\).

4. Avec des doublons, la methode echoue : sur [2, 2, 2, 1, 2] et [2, 1, 2, 2, 2], on a \(t[g] = t[m] = t[d] = 2\) dans les deux cas, sans pouvoir decider quelle moitie est triee. On est alors reduit a decrementer \(d\) d'un cran, ce qui donne \(\Theta(n)\) dans le pire cas (liste constante sauf un element). C'est une borne inferieure : aucun algorithme ne peut faire mieux, puisqu'il faut potentiellement examiner tous les elements egaux.

from math import cos, log, sqrt, ceil, log2

def zero(f, a, b, eps=1e-12):
    """Zero de f dans [a, b]. Precondition : f continue et f(a)*f(b) < 0."""
    fa, fb = f(a), f(b)
    if fa == 0:
        return a
    if fb == 0:
        return b
    if fa * fb > 0:
        raise ValueError("f(a) et f(b) doivent etre de signes opposes")
    n = 0
    while b - a > eps:
        m = (a + b) / 2
        fm = f(m)
        if fm == 0:
            return m
        if fa * fm < 0:
            b = m
        else:
            a, fa = m, fm
        n += 1
    return (a + b) / 2

r1 = zero(lambda x: cos(x) - x, 0, 1)
r2 = zero(lambda x: x**3 - 2, 0, 2)
r3 = zero(lambda x: log(x) - 1, 1, 4)
print(r1, r2, r3)
assert abs(cos(r1) - r1) < 1e-10
assert abs(r2 - 2**(1/3)) < 1e-10
assert abs(r3 - 2.718281828459045) < 1e-10

1. Hypotheses : \(f\) continue sur \([a,b]\) et \(f(a)f(b) < 0\). Le theoreme des valeurs intermediaires garantit alors l'existence d'un zero dans \(]a,b[\), et l'invariant « \(f(a)f(b) < 0\), donc \([a,b]\) contient un zero » est preserve a chaque etape.

2. La longueur de l'intervalle est divisee par 2 a chaque tour : \(b_n - a_n = \frac{b_0-a_0}{2^n}\). Pour atteindre \(\varepsilon\), il faut \[ n \ge \log_2\!\left(\frac{b_0-a_0}{\varepsilon}\right). \] Pour \(b_0-a_0 = 1\) et \(\varepsilon = 10^{-12}\) : \(n \ge 40\). La convergence est lineaire : chaque iteration gagne exactement un bit de precision, soit environ 0,3 decimale.

for eps in (1e-3, 1e-6, 1e-12):
    print(eps, ceil(log2(1/eps)))     # 10, 20, 40 iterations

4. Si \(f(a)\) et \(f(b)\) sont de meme signe, on leve une exception : il peut y avoir zero, deux, ou un nombre pair de racines, et la dichotomie ne saurait laquelle poursuivre. Sur \(f(x) = x^2 - 1\) et \([-2, 2]\), \(f(-2) = f(2) = 3 > 0\) alors qu'il y a deux racines.

Si \(f\) est discontinue, la methode converge toujours, mais vers un point de discontinuite avec changement de signe, et non vers un zero. Par exemple \(f(x) = 1/x\) sur \([-1, 1]\) verifie \(f(-1)f(1) < 0\) : la dichotomie converge vers 0, ou \(f\) n'est meme pas definie. La continuite est donc essentielle, et il faut toujours verifier a posteriori que \(|f(r)|\) est effectivement petit.

def morceaux(longueurs, L):
    """Nombre de morceaux de longueur L decoupables. Theta(n)."""
    if L <= 0:
        return float("inf")
    return sum(l // L for l in longueurs)

def longueur_max(longueurs, k):
    """Plus grande longueur L telle qu'on obtienne au moins k morceaux. 0 si impossible."""
    g, d = 1, max(longueurs)
    reponse = 0
    while g <= d:
        m = (g + d) // 2
        if morceaux(longueurs, m) >= k:
            reponse = m              # m convient, essayons plus grand
            g = m + 1
        else:
            d = m - 1                # m est trop grand
    return reponse

barres = [802, 743, 457, 539]
assert longueur_max(barres, 11) == 200
assert morceaux(barres, 200) == 4 + 3 + 2 + 2      # 11 morceaux
assert morceaux(barres, 201) == 10                 # un de moins : 200 est optimal

import random
def naif(longueurs, k):
    for L in range(max(longueurs), 0, -1):
        if morceaux(longueurs, L) >= k:
            return L
    return 0
for _ in range(200):
    b = [random.randint(1, 200) for _ in range(random.randint(1, 8))]
    k = random.randint(1, 20)
    assert longueur_max(b, k) == naif(b, k)
print("dichotomie sur le resultat validee")

2. Decroissance. Pour \(L \le L'\) et tout \(i\), on a \(\lfloor \ell_i/L' \rfloor \le \lfloor \ell_i/L \rfloor\) (la fonction \(x \mapsto \lfloor \ell/x\rfloor\) est decroissante sur \(\mathbb{N}^*\)). En sommant, \(\texttt{morceaux}(\ell, L') \le \texttt{morceaux}(\ell, L)\).

Par consequent le predicat « \(\texttt{morceaux}(\ell, L) \ge k\) » est vrai puis faux quand \(L\) croit : il est monotone, donc dichotomisable. On cherche le dernier vrai, d'ou la memorisation dans reponse.

4. Complexite. \(\Theta(\log(\max \ell_i))\) iterations, chacune coutant \(\Theta(n)\) : total \(\Theta(n\log(\max \ell_i))\). Ici \(4 \times 10 = 40\) operations, contre \(802 \times 4 = 3208\) pour la recherche lineaire descendante. Sur des longueurs de l'ordre de \(10^9\), le gain est decisif : 30 iterations au lieu d'un milliard.

1. Fusionner les deux listes jusqu'a la position mediane : \(\Theta(m+n)\) en temps, \(\Theta(1)\) en memoire si l'on ne stocke pas la fusion. Correct, mais on peut faire bien mieux.

2. Idee. Une coupure partage l'union en une partie gauche et une partie droite de tailles fixees. Si l'on prend \(i\) elements de \(A\) et \(j = k - i\) elements de \(B\) (avec \(k = \lceil (m+n)/2 \rceil\)), la coupure est valide lorsque

\[ A[i-1] \le B[j] \quad\text{et}\quad B[j-1] \le A[i], \] avec les conventions \(A[-1] = -\infty\) et \(A[m] = +\infty\). La mediane se lit alors aux frontieres. Il reste a trouver le bon \(i\) : par dichotomie, car la condition est monotone en \(i\).

import random
from math import inf

def mediane_deux_listes(A, B):
    """Mediane de l'union de deux listes triees. Theta(log(min(m, n)))."""
    if len(A) > len(B):
        A, B = B, A                      # on dichotomise sur la PLUS COURTE
    m, n = len(A), len(B)
    if m + n == 0:
        raise ValueError("listes vides")
    k = (m + n + 1) // 2                 # taille de la partie gauche
    g, d = 0, m
    while g <= d:
        i = (g + d) // 2                 # elements pris dans A
        j = k - i                        # elements pris dans B
        Ag = A[i-1] if i > 0 else -inf
        Ad = A[i]   if i < m else  inf
        Bg = B[j-1] if j > 0 else -inf
        Bd = B[j]   if j < n else  inf
        if Ag <= Bd and Bg <= Ad:        # coupure valide
            maxg = max(Ag, Bg)
            if (m + n) % 2 == 1:
                return float(maxg)
            return (maxg + min(Ad, Bd)) / 2
        if Ag > Bd:
            d = i - 1                    # on a pris trop d'elements dans A
        else:
            g = i + 1                    # pas assez

    raise RuntimeError("les listes ne sont pas triees")

# 4. verification exhaustive
def mediane_naive(t):
    u = sorted(t); n = len(u)
    return float(u[n//2]) if n % 2 else (u[n//2 - 1] + u[n//2]) / 2

for _ in range(3000):
    A = sorted(random.choices(range(20), k=random.randint(0, 7)))
    B = sorted(random.choices(range(20), k=random.randint(0, 7)))
    if A or B:
        assert mediane_deux_listes(A, B) == mediane_naive(A + B)
print("mediane de deux listes triees validee")

3. Invariant et correction. L'invariant est : s'il existe une coupure valide, alors elle correspond a un \(i \in [g, d]\).

• Initialisation : \([g,d] = [0,m]\) contient toutes les valeurs possibles de \(i\).
• Conservation : supposons \(A[i-1] > B[j]\). Pour tout \(i' \ge i\), on a \(A[i'-1] \ge A[i-1] > B[j] \ge B[k-i'-1+1]\)... plus simplement : augmenter \(i\) augmente \(A[i-1]\) (croissance de \(A\)) et diminue \(j\), donc diminue \(B[j]\). La condition \(A[i-1] \le B[j]\) ne peut donc que s'aggraver : aucun \(i' \ge i\) ne convient, et d = i - 1 preserve l'invariant. Le cas symetrique est analogue.
• Terminaison : le variant \(d-g+1\) decroit strictement.
• Conclusion : une coupure valide existe toujours (la coupure « vraie », celle du tri fusionne, en est une), donc la boucle sort par le return. La mediane vaut \(\max(A[i-1], B[j-1])\) si le total est impair — c'est le plus grand element de la moitie gauche, qui contient \(\lceil (m+n)/2\rceil\) elements — et la moyenne avec \(\min(A[i], B[j])\) sinon.

Complexite. La dichotomie porte sur \(i \in [0, m]\) avec \(m = \min(|A|,|B|)\), et chaque tour coute \(\Theta(1)\) : total \(\Theta(\log(\min(m,n)))\). Pour deux listes d'un milliard d'elements, c'est 30 operations contre \(2\cdot10^9\) pour la fusion.