Recherche d'un élément dans un tableau : algorithmes itératifs et récursifs

Recherche d’un élément dans un tableau

La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :

  • La recherche linéaire itérative ;
  • La recherche linéaire récursive ;
  • La recherche dichotomique itérative ;
  • La recherche dichotomique récursive.

Travail à faire

  • Implémenter en Python les cinq algorithmes suivants et répondre aux questions.
Penser à donner la spécification de chacune des fonctions et écrire une série des tests pour chacune d’elles.

Recherche séquentielle (ou linéaire)

La recherche séquentielle (ou linéaire) consiste à comparer la valeur recherchée à toutes les valeurs présentes dans le tableau.

Recherche séquentielle itérative

Algorithme 1

Fonction : recherche(tab, valeur)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début i ⟵ 0
i_val ⟵ -1
nb ⟵ Longueur(tab)
TantQue i < nb Faire
Si tab[i] = valeur Alors
i_val ⟵ i
FinSi
i ⟵ i + 1
FinTantQue
Renvoyer i_val
Fin

  1. Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 8, 3, 5, 9] et val = 3.

  2. Démontrer que l’algorithme se termine.

  3. Démontrer que l’algorithme est correct.

  4. Démontrer que l’algorithme est en O(N).

  5. Comment pourrait-on améliorer l’efficacité de cet algorithme ?

Algorithme 2

Fonction : recherche(tab, valeur)
Action : recherche de la valeur « valeur » dans le tableau « tab »
Début
trouvé ⟵ Faux
i ⟵ 0
TantQue i < nb et (Non trouvé) Faire
Si tab[i] = valeur Alors
trouvé ⟵ Vrai
Sinon
i ⟵ i + 1
FinSi
FinTantQue
Si trouvé = Vrai Alors
Renvoyer i
Sinon
Renvoyer -1
Fin

  1. Expliquer pourquoi l’algorithme 2 est plus efficace que l’algorithme 1.

Recherche séquentielle récursive

Algorithme 3

Fonction : recherche(tab, valeur, i)
Action : recherche la valeur « valeur » dans le tableau « tab » à l’aide de l’indice i.
Début nb ⟵ Longueur(tab)
Si i == nb Alors
Renvoyer -1
Sinon
Si tab[i] = valeur Alors
Renvoyer i
Sinon
Renvoyer recherche(tab, valeur, i + 1)
FinSi
FinSi
Fin

  1. Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 8, 3, 5, 9], i = 0 et val = 3.
    Établir, en particulier, l’arbre des appels.

Recherche dichotomique

Dès que le nombre de données devient important, la recherche séquentielle n’est plus envisageable. Sa complexité en $O(N)$ pénalise les autres traitements qui l’utilisent. Il faut diminuer le temps de traitement par l’emploi d’algorithmes plus performants, comme celui de la recherche dichotomique.

La recherche dichotomique est basée sur le principe de « diviser pour régner ». On divise l’ensemble de recherche en deux sous-ensembles égaux. On détermine ensuite dans quel sous-ensemble doit se trouver la valeur recherchée, puis on poursuit la recherche dans ce sous-ensemble.
Le préalable à la méthode de recherche dichotomique est de disposer d’un ensemble trié de données, car la détermination du sous-ensemble dans lequel se poursuit la recherche se fait par comparaison entre la valeur recherchée et les valeurs de début et de fin du sous-ensemble.
La division par deux de l’ensemble de données de recherche à chaque appel indique que la complexité est en $O(\log N)$.

Recherche dichotomique itérative

Algorithme 4

Fonction : recherche(tab, valeur)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début trouvé ⟵ FAUX
résultat ⟵ -1
gauche ⟵ 0
droite ⟵ Longueur(tab) - 1
TantQue (gauche <= droite) ET (NON trouvé) Faire
milieu ⟵ (droite + gauche) // 2
Si tab[milieu] = valeur Alors
resultat ⟵ milieu
trouvé ⟵ VRAI
SinonSi tab[milieu] < valeur Alors
gauche ⟵ milieu + 1
Sinon
droite ⟵ milieu - 1
FinSi
FinTantQue
Renvoyer résultat
Fin

  1. Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 3, 5, 8, 9] et val = 3.

  2. Démontrer que l’algorithme se termine.

  3. Démontrer que l’algorithme est correct.

  4. Démontrer que l’algorithme est en $O(\log_2 N)$.

Recherche dichotomique récursive

Algorithme 5

Fonction : recherche(tab, valeur, gauche, droite)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début Si gauche > droite Alors
Renvoyer -1
Sinon
milieu ⟵ (droite + gauche) // 2
Si tab[milieu] = valeur Alors
Renvoyer milieu
SinonSi tab[milieu] < valeur
Renvoyer recherche(tab, valeur, milieu + 1, droite)
Sinon
Renvoyer recherche(tab, valeur, gauche, milieu - 1)
FinSi
FinSi
Fin

  1. Décrire le fonctionnement de l’algorithme pour les valeurs tab = [1, 3, 5, 8, 9], gauche = 0, droite = 4, et val = 3.

Application

Écrire un programme de devinette : l’utilisateur choisit un nombre au hasard (compris entre 1 et 50) et l’ordinateur doit découvrir ce nombre. Faire en sorte que le nombre de tentatives de l’ordinateur lui permette de trouver la bonne valeur à coup sur (choisir de façon pertinente ce nombre).
Récursivité  Recherche linéaire  Recherche dichotomique  Complexité  Terminaison  Correction 

Voir également