Programmes de recherche

Recherche standard

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.

Voici le lien vers le programme AlgoTouch. 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 la recherche avec sentinelle est simple. Il consiste à remplacer la dernière valeur du tableau par la valeur recherchée. Ainsi, il suffit de parcourir le tableau jusqu’à trouver cette valeur. Puis vérifier que c’est bien la valeur cherchée et non celle qui a été placée volontairement en “sentinelle” (d’ou le nom de cet algorithme).

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

Illustration de la recherche avec sentinelle

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 en fin de tableau.

Recherche dichtomique

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. Comparer la valeur cherchée avec cette valeur pour déterminer si la recherche est fructueuse.

 

Voici le lien sur le programme AlgoTouch. 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.

Pour une recherche par dichotomie, le tableau de valeur doit être trié.

Recherche d’une séquence

Le problème est de chercher une séquence de valeurs dans un grand tableau. La figure ci-contre donne un exemple. On recherche la suite de valeurs 99, 100, 101 dans le tableau t. Cette suite existe et se trouve à l’indice 2.

Recherche des valeurs du tableau x dans le tableau t

Pour effectuer cette recherche, l’algorithme consiste à comparer les valeurs du tableau x avec le même nombre de valeurs du 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.

Le programme RechMotif propose une mise en oeuvre avec AlgoTouch. Une boucle principale parcourt le tableau t avec un indice k. Elle appelle une macro (boucle aussi) qui compare les valeurs de t à partir de k (avec un 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