Chapitre 2: Algorithmes de recherche

Commençons par créer une liste d’éléments pour cela nous allons écrire une fonction pour créer facilement des listes de mots.

from itertools import product
from string import ascii_uppercase as alphabet

def lister_mots(l=3):
    """Renvoie une liste ordonnés de mots ayant l lettres"""
    return [''.join(lettres) for lettres in product(alphabet, repeat=l)]

mots5 =  lister_mots(5)
# le nombre de noms générés est exponentiel par rapport à sa longueur
assert len(mots5) == 26**5
print(len(mots5), "mots")
print("Voici les sept premiers")
print(mots5[:7])
print("Et les sept derniers")
print(mots5[-7:])

11881376 mots
Voici les sept premiers
['AAAAA', 'AAAAB', 'AAAAC', 'AAAAD', 'AAAAE', 'AAAAF', 'AAAAG']
Et les sept derniers
['ZZZZT', 'ZZZZU', 'ZZZZV', 'ZZZZW', 'ZZZZX', 'ZZZZY', 'ZZZZZ']

Algorithme de recherche dans un tableau non trié

Nous allons voir comment chercher une valeur dans un tableau par une méthode de parcours du tableau: la recherche en table.

Cet algorithme naïf est couteux, mais on ne peut pas faire mieux si les données ne sont pas triées.

On parcourt l’ensemble du tableau et on s’arrête lorsqu’on trouve l’élément.

Dans une fonction le return est définitif, on peut donc facilement arrêter la boucle dès que la valeur est trouvée. Si on est arrivé au bout de la boucle on est donc certains que l’élément cherché n’est pas présent.

def recherche(élément, liste):
    """Fonction de recherche de l'élément dans la liste

    Arguments
    ---------
    élement: str
        l'élément cherché
    l: liste
        la liste dans laquelle on cherche
    Retourne
    --------
    bool
        True si l'élément est trouvé et False sinon
    """
    for e in liste:
        if e == élément:
            return True
    return False

Appelons la fonction sur un mot présent dans le tableau.

recherche("EULER", mots5)

EULER trouvé en 2186982 tours de boucle.

True

Regardons maintenant, si le mot n’est pas trouvé.

recherche("€UL€R", mots5)

€UL€R non trouvé en 11881376 tours de boucle.

False

La recherche dichotomique

Nous allons maintenant étudier l’algorithme de recherche par dichotomie. On peut comparer ça à une recherche dans un dictionnaire (qui a eu la bonne idée d’être trié!)

Principe

La recherche dichotomique ou recherche par dichotomie, est un algorithme de recherche pour trouver la position d’un élément dans un tableau trié. Le principe est le suivant : comparer l’élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente. Source Wikipedia

Définition de la fonction de recherche

def recherche_dichotomique(élément, liste):
    N = len(liste)
    
    # on initialise les indices début 
    # et fin aux extrémités de la liste
    début = 0
    fin = N - 1
    
    while début <= fin and fin < N:
        # On se place au milieu de la liste
        milieu = (début + fin) // 2 # il, s'agit d'une division entière
        # trois cas possibles
        
        if liste[milieu] < élément:       
            début = milieu + 1
        elif liste[milieu] > élément: 
            fin = milieu - 1
        else:
            return True
    return False

Appels de la fonction

Recherchons le mot EULER de la liste.

recherche_dichotomique('EULER', mots5)

EULER trouvé en 23 tours de boucle.

True

Incroyable on a trouvé en 23 fois au lieu de 2186982 avec la recherche en table.

recherche_dichotomique('€UL€R', mots5)

€UL€R non trouvé en 24 tours de boucle.

False

24 tours au lieu de 11881376 dans le pire cas: le mot est absent.

L’algorithme de recherche dichotomique est incroyablement plus efficace que l’algorithme de recherche en table.

Il s’agit d’un logarithme ayant une complexité en $log_2 (n)$ , c’est-à-dire le nombre de fois qu’il faut couper la liste en deux pour qu’elle ne contienne qu’un élément.

Par exemple:

• si n= $8$ : $log_2(8) = 3$
• si n= $256$ : $log_2(256) = 8$
• si n= $1024$ : $log_2 (1024) = 10$
• si n= $11881376$ : $log_2 (11881376) = 23,5$

Au lieu de 11881376 d’opérations, on en effectue 24 au maximum!

Complexité temporelle

Comme on l’a vu, si on utilise un tableau trié, la recherche dichotomique est beaucoup plus efficace que la recherche en table. Cela se traduit par un temps d’exécution infime en raison de sa complexité logarithmique.

%%timeit -n1 -r1
recherche('€UL€R', mots5)

€UL€R non trouvé en 11881376 tours de boucle.
492 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

%%timeit -n1 -r1
recherche_dichotomique('€UL€R', mots5)

€UL€R non trouvé en 24 tours de boucle.
99.3 µs ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)