Chapitre 3 : Techniques de Recherche dans un Vecteur

Introduction et Objectifs

Objectif général : Bien comprendre les techniques de recherche dans un vecteur (tableau unidimensionnel).

Objectif spécifique : Bien maîtriser les techniques de recherche séquentielle et dichotomique.

I. Recherche séquentielle linéaire

Il s’agit de rechercher un élément dans un vecteur en effectuant un parcours séquentiel (élément par élément depuis le début). La fonction correspondante est la suivante :

fonction recherche_sequentielle(V: vecteur, n, val, pos: entier): booléen
  début
    i ← 1
    tant que i <= n et val ≠ V[i] faire
      i ← i + 1
    fin tant que

    si val = V[i] alors
      recherche_sequentielle ← vraie
      pos ← i
    sinon
      recherche_sequentielle ← faux
    fin si
  fin

Temps favorable (Tn) : La complexité temporelle est linéaire car l’algorithme parcourt au pire des cas tout le tableau.

II. Recherche séquentielle avec sentinelle

L’idée de la sentinelle est de placer la valeur recherchée à la toute fin du tableau (qui doit avoir une case supplémentaire) pour éviter de tester le débordement de l’indice lors de la boucle tant que.

fonction recherche_sequentielle_sentinelle(V: vecteur, N, val, pos: entier): booleen
  var i: entier
  debut
    i ← 1
    V[N+1] ← val // Placement de la sentinelle

    tant que val ≠ V[i] faire
      i ← i + 1
    fin tant que

    si i <= N alors // on a trouvé avant la sentinelle
      recherche_sequentielle_sentinelle ← vraie
      pos ← i
    sinon
      recherche_sequentielle_sentinelle ← faux
    fin si
  fin

III. Recherche dichotomique

La recherche dichotomique suppose que le vecteur dans lequel on recherche une valeur val donnée est trié. Par exemple, trié dans l’ordre croissant.

Le principe divise systématiquement l’intervalle de recherche par 2 (dichotomie) :

1. Calculer le milieu de l’intervalle.
2. Si la valeur du milieu correspond à la valeur cherchée, alors on arrête.
3. Si la valeur du milieu est strictement supérieure à la valeur cherchée, on continue la recherche dans la moitié gauche (indices de min à milieu - 1).
4. Si la valeur du milieu est strictement inférieure à la valeur cherchée, on continue la recherche dans la moitié droite (indices de milieu + 1 à max).
5. Tant qu’on n’a pas trouvé, reprendre ces actions jusqu’à ce que l’intervalle soit vide (min > max).

fonction rech(V: vecteur, n, val, pos: entier): booléen
  var mil, min, max: entier
  trouve: booléen
  debut
    min ← 1
    max ← n
    trouve ← faux

    tant que (min <= max) et (non trouve) faire
      mil ← (min + max) div 2
      si val < V[mil] alors
        max ← mil - 1
      sinon
        si val > V[mil] alors
          min ← mil + 1
        fin si
      fin si
      trouve ← (val = V[mil])
    fin tant que

    rech ← trouve
  fin

IV. Travaux dirigés

• Exercice 1 : Que fait l’algorithme donné en cours illustrant une boucle Pour i complète qui continue même après avoir trouvé l’élément ? (Optimisation possible avec un Tantque).
• Exercice 2 : Développer l’algorithme qui permet de saisir et de stocker 100 réels puis qui affiche la valeur du plus petit ainsi que sa position d’apparition.
• Exercice 3 :
  1. Développer une procédure qui permet de saisir 100 réels.
  2. Développer une procédure qui prend en paramètre ce tableau et qui le trie.
  3. Développer une fonction renvoyant un booléen et appliquant la méthode dichotomique.