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

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.

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. :)