Recherche dans une liste, l'algorithme naïf

//déclarations
val: Valeur cherchée (entier)
i: Entier
liste : liste de N entiers triés
retour : Booléen
			 
//initialisation
retour ← faux
i ← 0
//Boucle de recherche
// La condition début inférieur ou égal à fin permet d'éviter de faire
// une boucle infinie si 'val' n'existe pas dans le tableau.
Tant que i <= N et retour est faux:
	si liste[i] == val:
		retour ← vrai
	i ← i+1				  
//Affichage du résultat
Si retour == vrai:
	Afficher "La valeur ", val , " est dans la liste."
Sinon:
	Afficher "La valeur ", val , " n'est pas dans la liste."
			

La dichotomie: généralités

Cette méthode, vous la connaissez tous!

Vous avez probablement joué au jeu :trouve un nombre entre 1 et 100. Vous avez commencé par proposer 50. Si on vous répond, c'est plus, vous proposez 75 puis si l'on vous répond c'est moins vous proposez 62... Vous êtes alors en train d'effectuer une recherche dichotomique !

Faire une recherche dichotomique, c'est chercher une valeur dans un tableau trié en prenant, à chaque étape, le milieu de l'ensemble des valeurs possibles pour éliminer la moitié des possibilités.

On peut résumer le principe de fonctionnement de l'algorithme de recherche dichotomique par le schéma suivant :

Il est aussi possible de représenter le principe de l'algorithme de recherche dichotomique avec le schéma suivant :

Faire tourner à la main

On rappelle l’algorithme de recherche dichotomique dans un tableau trié.

On dispose d’un tableau d’éléments triés par ordre croissant.

fonction appartient(tableau, element)

    gauche = 0
    droite = dernier indice
    trouvé = faux
    # AVANT

    Tant que gauche <= droite et que trouvé = faux 
        milieu = (gauche + droite) // 2
        # ICI
        si tableau[milieu] = element alors trouvé = vrai
        sinon si tableau[milieu] < element alors gauche = milieu + 1
        sinon droite = milieu - 1
        # LA
    Retourner trouvé

Programmer

def dichotomie(tableau: list, element: int) ->int:
    '''
    cette fonction....
    pré condition: ....
    post condition:.....
    '''
    gauche = 0
    droite = 
    while .......:
        milieu = ....... // 2
        if ............:
            return True
        elif.......:
            gauche =..............
        else:
            droite = ................
    return False
assert dichotomie([1,3,5,9,12,16,89],3)==True
assert dichotomie([1,3,5,9,12,16,89],52)==False

    

Complexité

Nous avons vu précédemment que l'algorithme naïf de recherche d'un nombre dans une liste triée avait dans le pire des cas une complexité linéaire. Voyons si la dichotomie est plus avantageuse de ce point de vu.

Complexité

Pour étudier la complexité, nous allons nous intéresser à la boucle : au niveau de la boucle, combien doit-on effectuer d'itérations pour un tableau de taille n dans le cas le plus défavorable (l'entier x n'est pas dans le tableau t) ?

Sachant qu'à chaque itération de la boucle on divise le tableau en 2, cela revient donc à se demander combien de fois faut-il diviser le tableau en 2 pour obtenir, à la fin, un tableau comportant un seul entier ? Autrement dit, combien de fois faut-il diviser n par 2 pour obtenir 1 ?

Mathématiquement cela se traduit par l'équation $\frac{n}{2^a}=1$ avec a le nombre de fois qu'il faut diviser n par 2 pour obtenir 1. Il faut donc trouver a !

A ce stade il est nécessaire d'introduire une nouvelle notion mathématique : le "logarithme base 2" noté $log_2$. Par définition $log_2(2^x)=x$

Nous avons donc :

$\frac{n}{2^a}=1$ => $n=2^a$ => $log_2(n)=log_2(2^a)=a$, nous avons donc $a=log_2(n)$

Nous pouvons donc dire que la complexité en temps dans le pire des cas de l'algorithme de recherche dichotomique est $O(log_2(n))$

Afin de pouvoir comparer l'efficacité des différents algorithmes, voici une représentation graphique des fonctions $y=x$ (en rouge), $y=x^2$ (en bleu) et $y=log_2(x)$ (en vert)

Comme vous pouvez le constater l'algorithme de recherche dichotomique est plus efficace que l'algorithme de recherche qui consiste à parcourir l'ensemble du tableau, car $x>log_2(x)$ quelque soit $x$. Cependant, il ne faut pas perdre de vu que dans le cas de la recherche dichotomique, il est nécessaire d'avoir un tableau trié, si au départ le tableau n'est pas trié, il faut rajouter la durée du tri.