Recherche dichotomique

DéfinitionProblème : RechercheTri

Entrée :

  • \(T\) : tableau d'entiers triés

  • \(x\) : entier

Sortie :

  • -1 si \(x\) n'est pas dans \(T\)

  • \(i \geqslant 0\) si \(i \in T\) et \(T[i]=x\)

FondamentalIdée de l'algorithme

On cherche ici à diviser le tableau en deux. En comparant l'élément central du tableau avec l'élément recherché, on va pouvoir choisir la moitié du tableau contenant l'élément cherché.

Visualisation d'une recherche dichotomique, où 4 est la valeur recherchée.Informations[1]
Exemple de liste

T est une liste. Ses éléments sont indicés de 0 à len(T). Son élément central est indicé pivot.

  • Si \(pivot > x\), alors on réitère sur T[:pivot].

  • Si \(pivot < x\), alors on réitère sur T[pivot:].

  • Si \(pivot = x\), alors on a trouvé \(x\).

SimulationAlgorithme

1
Fonction RechercheDico(T, x):
2
  Si taille(T) = 0 alors renvoyer -1
3
  Si taille(T) = 1 alors
4
    Si T[0] = x alors renvoyer 0
5
    Sinon renvoyer -1
6
  pivot <- partie_entiere(taille(T)/2)
7
  Si T[pivot] = x alors renvoyer pivot
8
  Si T[pivot] > x alors
9
    Renvoyer RechercheDico(T[:pivot], x)
10
  Sinon
11
    resultat <- RechercheDico(T[pivot:], x)
12
    Si resultat = -1 alors renvoyer -1
13
    Sinon renvoyer pivot + resultat

Cet algorithme est de complexité \(\mathcal{O}(\log_{2}n)\) avec \(n=\text{taille}(T)\).

Preuve :

On considère le nombre de comparaisons comme étant la mesure de complexité. Si \(T(x)\) est le nombre de comparaisons nécessaires pour une liste de taille \(x\), alors on a au plus \(T(n)=1+T(n/2)\) car on effectue une comparaison (on compare le pivot) avant de réduire la taille de notre liste.

On pose \(k\) tel que \(2^k \leqslant n < 2^{k+1}\)

  • Donc \(T(2^k) \leqslant T(n) < T(2^{k+1})\) (car \(T\) est une fonction croissante).

  • Donc \(T(2^{k+1})=1+T(2^{k+1}/2)=1+T(2^k)\).

  • Donc \(T(n) \approx T(2^k)\). Pour trouver la valeur de \(T(n)\), il suffit de trouver la valeur de \(T(2^k)\).

Soit \(u_k\) la suite définie par \(u_k=T(2^k)\), on peut déterminer la relation de récurrence avec \(T(2^{k+1})=T(2^k)+1\). On obtient \(u_{k+1}=u_k+1\).

  • \((u_k)\) est donc une suite arithmétique de premier terme \(u_0=T(2^0)=1\) et de raison \(r=1\).

  • Donc \(u_k=u_0+k \times r=1+k\).

Comme \(u_k=T(2^k)\) et \(u_k=k+1\), on en déduit que \(T(2^k)=k+1\).

  • Or, on rappelle que si \(2^k=n\) alors \(k=\log_{2}n\).

  • Donc l'équation \(2^k \leqslant n < 2^{k+1}\) devient \(k \leqslant \log_{2}n < k+1\).

  • Donc \(k+1= \lceil \log_{2}n \rceil\).

Ainsi se conclut notre preuve.

SimulationCode Python

1
def recherche_dico(T, x):
2
    """
3
    Recherche la valeur x dans un tableau T trié
4
    :param T: Tableau trié
5
    :param x: Élément à rechercher
6
    :return: Indice de l'élément recherché
7
    """
8
    if len(T) == 0:
9
        return -1
10
    if len(T) == 1:
11
        if T[0] == x:
12
            return 0
13
        else:
14
            return -1
15
    pivot = len(T) // 2
16
    if T[pivot] == x:
17
        return pivot
18
    # On choisit le bon côté
19
    if T[pivot] > x:
20
        return recherche_dico(T[:pivot], x)
21
    else:
22
        # On stocke le résultat au cas où c'est -1
23
        resultat = recherche_dico(T[pivot:], x)
24
        if resultat == -1:
25
            return -1
26
        else:
27
            return pivot + resultat
28
29
30
T = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
31
print(recherche_dico(T, 3))
32
print(recherche_dico(T, 0))
33
print(recherche_dico(T, 5))
34
print(recherche_dico(T, 8))
35