Programmes de recherche

  • Accueil   /  
  • Programmes de recherche

Recherche séquentielle

Le principe de la recherche séquentielle consiste à parcourir le tableau de valeur. Le parcours s’interrompt si la valeur est trouvée ou si toutes les valeurs du tableau ont été consultées. Le programme demande une valeur à l’utilisateur. Si la valeur est trouvée, l’indice associé est affichée. Sinon, le programme indique que la valeur est absente.
Recherche séquentielle d'une valeur dans un tableau

Recherche avec sentinelle

Le principe de cette recherche avec une sentinelle est simple. Il consiste à remplacer provisoirement la dernière valeur du tableau par la valeur recherchée. Cette valeur est placée volontairement en « sentinelle » (d’où le nom de cet algorithme) pour la trouver dans tous les cas. Ainsi, il suffit de parcourir le tableau (d’entiers ou caractères) jusqu’à trouver cette valeur. Puis vérifier que c’est bien la valeur cherchée et non celle qui a été placée en « sentinelle ».

Illustration de la recherche avec sentinelle

Le programme demande une valeur. Si la valeur est trouvée, il affiche son indice. Sinon, il indique que la valeur est absente.

La valeur à chercher (val) remplace la dernière valeur du tableau qui est sauvegardée dans la variable tmp. En fin de parcours la valeur contenue dans tmp est remise à sa place initiale dans le tableau (array).

Recherche par dichotomie

Parfois le tableau sur lequel doit s’effectuer la recherche est trié (par ordre croissant par exemple). Dans ce cas, on peut améliorer l’algorithme de recherche en effectuant moins de comparaisons.

Le principe est le suivant: comparer la valeur cherchée avec celle se situant au milieu du tableau :

  • si la valeur est plus petite, rechercher dans le sous tableau des valeurs inférieures;
  • si la valeur est plus grande ou égale, rechercher dans le sous tableau des valeurs supérieures ou égales.

L’espace de recherche dans les sous tableaux successifs diminue à chaque étape. Il faut alors arrêter si le sous tableau contient une seule valeur. Il suffit alors de comparer la valeur cherchée avec cette valeur pour déterminer si la recherche est fructueuse.

Pour une recherche par dichotomie, le tableau de valeur doit être trié.
Comme dans les exemples précédents, le programme demande une valeur. Si la valeur est trouvée, il affiche son indice. Sinon, il indique que la valeur est absente.

Recherche d'une séquence

Le problème est de chercher une séquence de valeurs dans un grand tableau. Par exemple, on recherche si la suite de valeurs 99, 100, 101 (stockées dans le tableau x) se trouve dans le tableau d’entiers t. Cette suite existe et se trouve à l’indice 2.
Recherche des valeurs du tableau x dans le tableau d'entiers t
Pour effectuer cette recherche, l’algorithme consiste à comparer les valeurs du tableau x avec le même nombre de valeurs dans le tableau t à partir de l’indice 0. Si la suite est différente, on recommence la recherche à partir de l’indice 1, etc. L’algorithme s’arrête si la recherche est fructueuse à un certain indice ou si toutes les comparaisons ont été effectuées.

Une boucle principale parcourt le tableau t avec l’indice k. Elle appelle une macro (de type boucle) qui compare les valeurs de t à partir de k (avec l’indice i ) avec les valeurs de x indexés par j. La variable ok passe à 1 (vrai) si la séquence x correspond.

Mise en oeuvre de l'algorithme de recherche de séquence