Un peu de recherche ne peut faire que du bien !!

Introduction du cours

Bonjour chers Zéros. :D

Si vous êtes ici, c'est que vous avez déjà envie de créer une fonction de recherche quelque part (rechercher un caractère ou un nombre dans un tableau en C, par exemple).
Eh bien je peux vous dire que c'est votre jour de chance, car vous venez de trouver un le tutoriel pour cela ( :p ), mais pour pouvoir me suivre à 100 %, vous devez avoir déjà pratiqué ne serait-ce qu'un tout petit peu de programmation quelconque.
Bien sûr, je ne vous apprendrai pas l'algorithme de recherche de Google, mais ces algorithmes sont très efficaces aussi, et peuvent s'avérer très utiles.
Ainsi, dans ce tutoriel je vous présenterai deux façons de rechercher :

• la recherche séquentielle ;

• la recherche dichotomique.

Alors accrochez vos ceintures, on décolle. :soleil:

• [EDIT le 11/07/2007] : Faute de frappe signalée par Thaxssillyi@

• [EDIT le 11/07/2007] : Oublie d'un "=" signalé par ????

La recherche séquentielle

En bons programmeurs que vous êtes, je vous demande de créer un algorithme de recherche d'un nombre dans une liste de nombres (qui peut aussi bien être une liste de caractères, puisque comme nous le savons tous, les caractères sont des nombres ^^ ).
Vous réfléchissez pendant 5 minimicronanosecondes, et vous me répondez qu'il faut parcourir toute la liste case par case pour être sûrs de n'oublier aucun caractère.
Eh bien vous venez de donner la définition de la recherche séquentielle !!
Comme nous l'avons dit précédemment, nous allons parcourir tous les nombres à la recherche du nombre souhaité.
Pour cela, nous allons bien sûr avoir besoin d'un test qui, appliqué à une case, vérifiera si le nombre recherché se trouve dans la case ou non.
Nous aurons aussi besoin d'une boucle, qui répétera l'opération de test autant de fois qu'il y a de cases.
Voici le code implémenté en C de la fonction de recherche, qui doit être appliqué à une liste tab[N] déjà remplie, où N est le nombre de cases du tableau (vous remplacerez tous les N par le nombre de cases que contient votre tableau.

long nbrRecherche=0, i=0, position=0; printf("Veuillez entrer le nombre recherché : ..."); scanf("%ld",&nbrRecherche); for(i=0; i<=N-1; i++) { if(tab[i]==nbrRecherche) { position=i+1; //Pour avoir le n° de la case où se trouve le nombre recherché i=2*N; //Condition pour sortir de la boucle } } if(i==2*N+1) { printf("Le nombre %ld se trouve dans la case n°%ld", nbrRecherche, position); } else { printf("Le nombre %ld ne se trouve pas dans ce tableau", nbrRecherche); }

Ce code présente, comme généralement tous les codes, des avantages et des inconvénients.
L'avantage, c'est qu'il peut être appliqué à n'importe quel tableau, qu'il soit trié ou non.
L'inconvénient, c'est qu'il est assez complexe.
Non pas complexe à comprendre, la preuve est que vous l'avez compris du premier coup ( :D ), mais complexe au niveau d'opérations faites. Ainsi, si votre N est grand, le programme fonctionnera, bien sûr, mais ça risque d'être assez long.
Supposons que je recherche un nombre qui ne se trouve pas dans le tableau, 825 par exemple, dans le tableau suivant :

25        56        89        235        45        78        412        10        23        12        87        96        47        101        589        412

le programme affichera :

Le nombre 825 ne se trouve pas dans ce tableau

Le programme a bien su que le nombre n'existait pas, mais seulement après N tours de boucle.
Alors imaginez que j'ai à chercher le mot zéro dans un dictionnaire qui fait 50 000 mots, eh bien on n'est pas sortis de l'auberge. :lol:
Et c'est justement ce que nous allons voir dans la partie suivante.

La recherche dichotomique

Ce titre assez barbant a sûrement fait fuir plusieurs programmeurs ambitieux ( :lol: ), mais je peux vous assurer que c'est un concept assez simple à comprendre.
Alors déjà, dans "dichotomie", on peut trouver le mot dictionnaire, et ce n'est pas du tout par hasard.
Je pense que vous avez tous déjà fait une recherche dans un dictionnaire.
Si je vous demande comment on y cherche le mot "chercher", vous allez tous me répondre d'une seule et même voix :

Citation : Quelqu'un ayant déjà cherché dans un dictionnaire

On ouvre le dictionnaire, si on tombe sur une page où les mots commencent par une lettre ultérieure à C, alors on ouvre une autre page entre le début du dictionnaire et la page déjà ouverte ; sinon, on ouvre une autre page entre la page ouverte et la fin.
Et on répète cette opération autant de fois qu'il le faut pour trouver le mot cherché...

Exact, c'est bien cela.
Et c'est exactement la méthode utilisée dans la recherche dichotomique. ^^
Dans un dictionnaire, les mots sont triés, ce qui est forcément une condition pour utiliser ce genre de recherche : le tableau doit impérativement être trié.
Vous avez plusieurs façons de trier les éléments d'un tableau, et plusieurs tutoriels sur ce site l'expliquent très simplement :

• Le tri par insertion ;

• Le tri de Shell ;

• Tri par insertion : le retour (OCaml) ;

• Le tri à paniers.

Maintenant que les éléments du tableau sont triés, je vous explique le fonctionnement de l'algorithme, chargé de recherche dichotomique dans un tableau rempli et trié, ceci dans l'ordre croissant tab[N], avec min=tab[0] et max=tab[N].
Comme pour notre recherche dans un dictionnaire, le programme va chercher dans une case au hasard, entre les deux bornes max et min. (On prendra leur milieu, pour avoir les mêmes chances des deux côtés.)
Si le nombre trouvé est inférieur au nombre recherché, le programme sait qu'on devra dorénavant le chercher dans la première moitié du tableau. Sinon, on sait maintenant qu'on devra le chercher dans la deuxième moitié.
On refait l'opération pour la moitié concernée, et ainsi de suite jusqu'à tomber sur une moitié qui ne contient qu'une seule case, et là, si notre nombre ne s'y trouve pas, c'est que le nombre n'est pas dans le tableau.
Avouez que vous avez vu plus facile ( :lol: ), mais ne vous inquiétez pas : si vous n'avez pas compris, vous comprendrez lorsque l'on fera l'implémentation en langage C. La voici, d'ailleurs :

/*N est le nombre d'éléments du tableau tab[], contenant des nombres classés par ordre croissant.*/ long nbrRecherche=0, sup=0, inf=0, demi=0, B=1; printf("Veuillez entrer le nombre recherché : ..."); scanf("%ld", &nbrRecherche) //On définit les bornes de la partie du tableau à considérer Sup = N - 1; Inf = 0; while(B) { /*demi désigne l'indice de l'élément à comparer. En bonne rigueur, il faudra veiller à ce que demi soit bien un nombre entier, ce qui pourra s'effectuer de différentes manières selon les langages.*/ demi = (sup + inf)/2; /*Si le nombre se situe avant le point de comparaison, alors la borne supérieure change, la borne inférieure ne bouge pas.*/ if(nbrRecherche < tab[demi]) { sup = demi - 1; } /*Sinon, c'est l'inverse*/ else { inf = demi + 1 } if( sup<inf || nbrRecherche=tab[demi]) { B=0 } } if{nbrRechercher == tab[demi]} { printf("Le nombre %ld se trouve dans la case n°%ld" nbrRecherche, demi+1); } else { printf("Le nombre %ld ne se trouve pas dans ce tableau", nbrRecherche); }

Par comparaison entre la recherche dichotomique et la recherche séquentielle, prenons l'exemple de tout à l'heure (un nombre qui ne se trouve pas dans la liste) :

12        24        35        48        57        61        70        79        83        85        87        96        99        101        412        931

Et faisons la trace du programme (le compte rendu de ses actions, si vous voulez :D ), et ce en cherchant le nombre 835 qui ne se trouve pas dans la liste.

• 1er tour de boucle : la liste contient 16 cases. Donc inf=0 et sup=15, et demi=7. La case n°7 est occupée par le nombre 79, qui est différent de 835 ; on a alors inf=demi+1=8.

• 2e tour de boucle : inf=8 et sup=15, et demi=11. La case n°11 est occupée par 96, qui est différent de 835 ; on a alors inf=demi+1=12.

• 3e tour de boucle : inf=12 et sup=15, et demi=13. La case n°13 est occupée par 101, qui est différent de 835 ; on a alors inf=demi+1=14.

• 4e : inf=14 et sup=15, et demi=14. La case n°14 est occupée par 412, qui est différent de 835 ; on a alors inf=demi+1=15.

• 5e tour de boucle : inf=15 et sup=15, et demi=15. La case n°15 est occupée par 931, qui est différent de 835 ; on a alors sup=demi-1=14.

• 6e tour de boucle : on a inf>sup, donc le programme écrit à l'écran :

  Le nombre 835 ne se trouve pas dans ce tableau

Et voilà : on peut remarquer que le programme a fait 6 tours de boucle pour savoir que le nombre recherché ne se trouve pas dans le tableau, contre 16 tours de boucle pour la recherche séquentielle.
Sauf que le problème avec cet algorithme, c'est que le tableau doit impérativement être trié auparavant. :'(
Mais il trouvera bien son utilité dans la recherche du mot "zéro", dans un dictionnaire de 50 000 mots par exemple. :D

Voilà : ce tuto touche à sa fin, et j'espère que vous avez bien compris le principe des deux recherches.
Pour bien l'assimiler, vous pourrez faire une recherche dichotomique dans un tableau dont les éléments sont triés dans l'ordre décroissant (j'ai traité le cas de la croissance), et essayer d'améliorer le code (eh oui, le code que je vous ai écrit plus haut n'est qu'une variante parmi de la recherche dichotomique plusieurs autres, mais le principe reste toujours le même ^^ ).
Quant à moi, je finis mon premier tuto pour le SDZ, et je m'en vois très fier.
N'hésitez pas à poster vos commentaires dans la rubrique appropriée. Vous pouvez aussi me contacter par MP si vous le souhaitez ;) .
Merci d'avoir lu jusqu'à la fin mon tutoriel, et à bientôt sur le Site du Zér0. :)

• #

Waouh !

Très heureux de voir que nos cours vous plaisent, déjà 3 pages lues aujourd'hui ! Vous pouvez continuer la lecture de nos cours en devenant un Roomie, un membre de la communauté d'OpenClassrooms. C'est gratuit !

Vous pourrez aussi suivre votre avancement dans le cours, faire les exercices et discuter avec les autres Roomies.

S'inscrire Se connecter

• Thématiques du cours : Algorithmique Programmation

Chaque cours est créé par un professeur ou un expert dans le domaine. Il est composé d'une ou plusieurs parties et peut comporter du texte, des images (schéma, illustration) et des vidéos. Chaque partie d'un cours certifiant est ponctuée d'exercices de 2 types : Des quiz corrigés automatiquement Des devoirs libres (exemple : créer un site web avec des consignes précises). Ces devoirs sont évalués par les pairs. Chaque devoir est corrigé 3 fois par 3 autres élèves, dans un processus en double aveugle, selon un barème fixé par le professeur. La note finale est la moyenne des 3 notes reçues sur le devoir. 50% des devoirs corrigés par les pairs obtiennent quasiment les 3 mêmes notes, avec une variance inférieure à 1. La recherche académique montre d'ailleurs que l'évaluation par les pairs peut être aussi précise que celle des professeurs.