Chercher dans un tableau
Chercher une information est l'une des tâches les plus fréquentes en informatique. Voyons les algorithmes de recherche les plus classiques.
Trouver le plus grand élément
L'idée : on suppose que le premier élément est le plus grand, puis on compare avec tous les autres. Chaque fois qu'on trouve plus grand, on le retient.
scores est un tableau vaut [42, 87, 15, 93, 61]
meilleur est un nombre vaut scores[0]
pour i de 1 à longueur(scores) - 1
si scores[i] > meilleur alors
meilleur vaut scores[i]
fin si
fin pour
affiche 'Meilleur score : ' + meilleur // 93
On part du premier élément, pas de 0 : si tous les scores étaient négatifs, partir de 0 donnerait un mauvais résultat.
Pour le plus petit, il suffit de changer > en <.
Question : Pour retenir où se trouve le maximum (son index) plutôt que sa valeur, que faut-il mémoriser dans la boucle ? — i. On mémorise l'index i ; la valeur se retrouve ensuite avec scores[indiceMax].
Chercher une valeur : la recherche séquentielle
On parcourt le tableau du début à la fin, et on s'arrête dès qu'on trouve :
prenoms est un tableau vaut ['Léa', 'Tom', 'Sam', 'Inès']
cherche est un texte
demande 'Quel prénom cherches-tu ? ' dans cherche
place est un nombre vaut -1
pour i de 0 à longueur(prenoms) - 1
si prenoms[i] = cherche alors
place vaut i
arrête
fin si
fin pour
si place >= 0 alors
affiche cherche + ' est à la place ' + (place + 1) + '.'
sinon
affiche cherche + ' n’est pas dans la liste.'
fin si
La valeur -1 sert à dire « pas trouvé », car aucun index ne vaut -1. Et arrête évite de continuer à chercher une fois la valeur trouvée.
CoddyRun a une fonction qui fait exactement ça : index_de(prenoms, 'Sam') renvoie 2, ou -1 si la valeur est absente.
La dichotomie : chercher beaucoup plus vite
Dans un tableau trié, on peut faire bien mieux. C'est la méthode du jeu « plus grand, plus petit » : on regarde au milieu, et on élimine la moitié du tableau à chaque fois.
fonction dichotomie(liste, valeur)
gauche est un nombre vaut 0
droite est un nombre vaut longueur(liste) - 1
milieu est un nombre
tant que gauche <= droite
milieu vaut arrondi_inferieur((gauche + droite) / 2)
si liste[milieu] = valeur alors
retourne milieu
sinon si liste[milieu] < valeur alors
gauche vaut milieu + 1
sinon
droite vaut milieu - 1
fin si
fin tant que
retourne -1
fin fonction
nombres est un tableau vaut [3, 8, 15, 21, 34, 42, 57, 63, 78, 91]
affiche dichotomie(nombres, 42) // 5
affiche dichotomie(nombres, 10) // -1
Pour 10 éléments, la recherche séquentielle peut demander 10 comparaisons ; la dichotomie en demande au plus 4. Pour un million d'éléments : un million contre... 20 ! C'est toute la puissance d'un bon algorithme.
Question : Pourquoi la dichotomie ne marche-t-elle que sur un tableau trié ? — Parce qu'elle décide de quel côté chercher en comparant avec le milieu. Si le tableau n'est pas trié, savoir que le milieu est plus petit ne dit rien sur la position de la valeur.
En résumé
- Maximum : partir du premier élément et retenir le plus grand rencontré.
- Recherche séquentielle : parcourir jusqu'à trouver ; -1 signifie « absent ».
- Dichotomie : sur un tableau trié, couper en deux à chaque étape. Beaucoup plus rapide.
