Algorithmes de recherches

1Recherche sequentielle et recherche dichotomique

Rechercher un element dans une collection est l'operation la plus courante en informatique. Selon que les donnees sont ou non ordonnees, le cout passe de \(\Theta(n)\) a \(\Theta(\log n)\) — un ecart qui, sur un million d'elements, separe un million d'operations de vingt.

Recherche sequentielle

def recherche_sequentielle(t, v):
    """Indice de la premiere occurrence de v dans t, ou -1. Theta(n)."""
    for i in range(len(t)):
        if t[i] == v:
            return i
    return -1

def appartient(t, v):
    """Version booleenne."""
    for x in t:
        if x == v:
            return True
    return False

def recherche_sentinelle(t, v):
    """Un seul test par tour. Modifie temporairement t."""
    t.append(v)                     # sentinelle
    i = 0
    while t[i] != v:
        i += 1
    t.pop()
    return i if i < len(t) else -1

Recherche dichotomique

def dichotomie(t, v):
    """Indice de v dans la liste TRIEE t, ou -1. Theta(log n).

    Precondition : t est triee par ordre croissant.
    """
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2             # indice median
        if t[m] == v:
            return m
        if t[m] < v:
            g = m + 1                # v est dans la moitie droite
        else:
            d = m - 1                # v est dans la moitie gauche
    return -1

2Dichotomie interactive, preuve et variantes

Preuve de la dichotomie

Version recursive

def dichotomie_rec(t, v, g=0, d=None):
    """Version recursive. Recursivite TERMINALE : la profondeur est Theta(log n)."""
    if d is None:
        d = len(t) - 1
    if g > d:
        return -1
    m = (g + d) // 2
    if t[m] == v:
        return m
    if t[m] < v:
        return dichotomie_rec(t, v, m + 1, d)
    return dichotomie_rec(t, v, g, m - 1)

Attention : passer des tranches t[:m] plutot que des indices couterait \(\Theta(n)\) par appel (copie), detruisant l'interet de la methode. On passe donc toujours des indices.

Recherche de bornes

Deux variantes essentielles quand la liste comporte des doublons ou que l'on veut inserer :

def borne_inf(t, v):
    """Plus petit indice i tel que t[i] >= v (len(t) si aucun). Theta(log n)."""
    g, d = 0, len(t)
    while g < d:
        m = (g + d) // 2
        if t[m] < v:
            g = m + 1
        else:
            d = m
    return g

def borne_sup(t, v):
    """Plus petit indice i tel que t[i] > v."""
    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, 7, 9]
assert borne_inf(t, 3) == 1
assert borne_sup(t, 3) == 4
assert borne_sup(t, 3) - borne_inf(t, 3) == 3      # nombre d'occurrences
assert borne_inf(t, 5) == 4                        # position d'insertion

Le module standard fournit ces deux fonctions sous les noms bisect.bisect_left et bisect.bisect_right.

3Dichotomier une propriete monotone

Dichotomie sur une fonction : recherche de seuil

La dichotomie ne s'applique pas qu'aux listes. Des qu'une propriete est monotone (fausse puis vraie), on peut chercher le seuil par dichotomie.

def premier_vrai(predicat, g, d):
    """Plus petit entier k de [g, d] tel que predicat(k) soit vrai.

    Precondition : predicat est croissant (faux ... faux vrai ... vrai).
    Theta(log(d - g)) appels au predicat.
    """
    while g < d:
        m = (g + d) // 2
        if predicat(m):
            d = m
        else:
            g = m + 1
    return g

# racine carree entiere sans utiliser sqrt
def racine_entiere(n):
    """Plus grand k tel que k*k <= n. Theta(log n)."""
    return premier_vrai(lambda k: k*k > n, 0, n + 1) - 1

assert racine_entiere(0) == 0
assert racine_entiere(15) == 3 and racine_entiere(16) == 4
for n in range(10000):
    r = racine_entiere(n)
    assert r*r <= n < (r+1)*(r+1)

# zero d'une fonction continue : dichotomie sur les reels
def zero(f, a, b, eps=1e-12):
    """Un zero de f dans [a, b], avec f(a) et f(b) de signes opposes.

    Theta(log((b-a)/eps)) evaluations de f.
    """
    fa = f(a)
    if fa == 0:
        return a
    while b - a > eps:
        m = (a + b) / 2
        fm = f(m)
        if fm == 0:
            return m
        if fa * fm < 0:          # le zero est dans [a, m]
            b = m
        else:
            a, fa = m, fm
    return (a + b) / 2

from math import cos
r = zero(lambda x: cos(x) - x, 0, 1)
print(r)                      # 0.7390851332151607
assert abs(cos(r) - r) < 1e-10

Le nombre d'iterations pour atteindre une precision \(\varepsilon\) sur un intervalle de longueur \(L\) est \(\lceil \log_2(L/\varepsilon)\rceil\) : environ 40 iterations pour \(L = 1\) et \(\varepsilon = 10^{-12}\). Cette methode est reprise et comparee a celle de Newton au chapitre 21.

Recherche dans un espace de solutions

def realisable(durees, k, capacite):
    """Peut-on repartir les taches en k groupes consecutifs de somme <= capacite ?"""
    if capacite < max(durees):
        return False
    groupes, courant = 1, 0
    for d in durees:
        if courant + d > capacite:
            groupes += 1                  # on ouvre un nouveau groupe
            courant = d
        else:
            courant += d
    return groupes <= k

def charge_minimale(durees, k):
    """Plus petite capacite realisable. Theta(n log(somme)) ."""
    g, d = max(durees), sum(durees)
    while g < d:
        m = (g + d) // 2
        if realisable(durees, k, m):
            d = m
        else:
            g = m + 1
    return g

assert charge_minimale([10, 20, 30, 40], 2) == 60      # [10,20,30] et [40]
assert charge_minimale([1, 1, 1, 1], 4) == 1
assert charge_minimale([7], 3) == 7

Comparaison des methodes de recherche

Le choix depend du profil d'utilisation : beaucoup de recherches et peu de modifications (liste triee), beaucoup des deux sans besoin d'ordre (hachage), les deux avec besoin d'ordre (arbre equilibre, hors programme de premiere annee).