Localiser efficacement une valeur dans un ensemble de données

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• définir le problème de recherche d’une valeur dans un tableau ;
• distinguer la présence, la position et le nombre d’occurrences d’une valeur ;
• concevoir une recherche séquentielle avec ou sans arrêt anticipé ;
• rechercher toutes les occurrences d’une valeur ;
• construire et tracer une recherche dichotomique ;
• expliquer pourquoi la recherche dichotomique exige un tableau trié ;
• calculer correctement l’indice du milieu ;
• mettre à jour les bornes gauche et droite sans perdre de valeur possible ;
• écrire les versions itérative et récursive de la recherche dichotomique ;
• comparer les méthodes selon le nombre d’opérations, la taille des données et leur organisation ;
• identifier les cas favorables, moyens et défavorables ;
• choisir la méthode de recherche adaptée à une situation donnée ;
• élaborer des jeux d’essai et détecter les erreurs de bornes.

Prérequis

• maîtriser les variables, conditions et boucles ;
• savoir déclarer et parcourir un tableau à une dimension ;
• connaître les fonctions, les paramètres et les valeurs de retour ;
• comprendre la division entière ;
• savoir construire une table de trace ;
• connaître le principe d’un appel récursif.

Plan du chapitre

13.1 Recherche séquentielle

13.2 Recherche dichotomique

13.3 Comparaison des méthodes

Applications, tables de trace, travaux dirigés, corrigés et synthèse

Organisation pédagogique indicative

Introduction aux algorithmes de recherche

Rechercher une information est une opération fondamentale en informatique. Un programme peut avoir besoin de vérifier l’existence d’un identifiant, de retrouver une note, de localiser un produit, de déterminer la position d’un nom ou de compter le nombre d’apparitions d’une valeur.

Le problème étudié dans ce chapitre consiste à rechercher une valeur appelée clé dans un tableau. Selon le besoin, l’algorithme peut retourner un booléen, l’indice de la première occurrence, la liste de toutes les positions ou le nombre d’occurrences.

Deux stratégies seront étudiées. La recherche séquentielle examine les éléments dans leur ordre de stockage et fonctionne sur tout tableau. La recherche dichotomique élimine la moitié de la zone restante à chaque étape, mais elle n’est correcte que si les données sont triées selon un ordre compatible avec les comparaisons.

13.1 Recherche séquentielle

13.1.1 Principe

La recherche séquentielle, également appelée recherche linéaire, consiste à comparer la clé recherchée avec les éléments du tableau, l’un après l’autre. Le parcours commence généralement au premier élément et avance jusqu’à la découverte de la valeur ou jusqu’à la fin du tableau.

Cette méthode ne suppose aucun ordre particulier. Elle peut donc être appliquée à un tableau trié, non trié, partiellement rempli ou contenant des doublons.

13.1.2 Parcours complet du tableau

Un parcours complet examine tous les éléments. Il est nécessaire lorsque l’objectif est de compter les occurrences, de trouver toutes les positions ou de vérifier une propriété portant sur l’ensemble du tableau.

Recherche de l’existence par parcours complet

Cette version reste correcte, mais elle continue à comparer les éléments après avoir trouvé la valeur. Lorsque seule l’existence ou la première position est demandée, un arrêt anticipé évite des opérations inutiles.

13.1.3 Arrêt dès que l’élément est trouvé

L’arrêt anticipé termine la recherche à la première occurrence. Il améliore le comportement dans les cas favorables, notamment lorsque la valeur se trouve près du début du tableau.

Version avec boucle TantQue

13.1.4 Table de trace détaillée

Considérons T = [14, 7, 22, 7, 31] et x = 22. La boucle s’arrête lorsque l’indice 2 est atteint.

La valeur 7 apparaît deux fois, mais une recherche de la première occurrence retourne l’indice 1 et ne poursuit pas jusqu’à l’indice 3.

13.1.5 Recherche de toutes les occurrences

Lorsque le tableau peut contenir des doublons, la première occurrence ne suffit pas toujours. Il faut alors parcourir tout le tableau et traiter chaque égalité.

Afficher toutes les positions

Les occurrences de 4 se trouvent aux indices 0, 2 et 4. Le compteur final vaut 3.

13.1.6 Retourner les positions dans un tableau

Si les positions doivent être réutilisées, elles peuvent être enregistrées dans un second tableau. Celui-ci possède au maximum n éléments, puisque chaque case du tableau d’origine peut correspondre à une occurrence.

Construire le tableau des positions

13.1.7 Recherche à partir d’une position

Dans certaines applications, on souhaite chercher la prochaine occurrence après une position donnée. Le point de départ devient alors un paramètre.

Rechercher à partir de debut

Cette fonction peut être appelée plusieurs fois afin de parcourir les occurrences successives sans recommencer systématiquement à l’indice 0.

13.1.8 Recherche avec sentinelle

La technique de la sentinelle place temporairement la valeur recherchée dans une case supplémentaire située après la partie utile du tableau. Elle simplifie la condition de boucle, mais elle exige une capacité disponible et la restauration éventuelle de la case utilisée.

Principe de la sentinelle

Cette variante est présentée pour la culture algorithmique. Dans un programme réel, elle doit être utilisée avec prudence afin de ne pas écrire en dehors de la capacité du tableau.

13.1.9 Version récursive

Une recherche séquentielle peut aussi être formulée récursivement. Le paramètre i indique la prochaine case à examiner.

Recherche séquentielle récursive

Cette version réalise les mêmes comparaisons que la version itérative, mais elle utilise un appel de fonction par élément examiné. La boucle est généralement plus adaptée à ce problème simple.

13.1.10 Cas particuliers et validation

13.2 Recherche dichotomique

13.2.1 Principe de division de l’espace de recherche

La recherche dichotomique, aussi appelée recherche binaire, exploite l’ordre des données. Elle compare la clé à l’élément situé au milieu de la zone encore possible. Selon le résultat, elle conserve la moitié gauche ou la moitié droite et élimine l’autre moitié.

L’espace de recherche est donc approximativement divisé par deux à chaque étape. Une grande quantité de données peut être éliminée après très peu de comparaisons.

13.2.2 Condition indispensable : tableau trié

La décision d’éliminer une moitié repose sur l’ordre du tableau. Dans un tableau trié par ordre croissant, toutes les valeurs situées à gauche du milieu sont inférieures ou égales à l’élément central, tandis que celles de droite sont supérieures ou égales.

Si le tableau n’est pas trié, une valeur plus petite que l’élément central peut se trouver à droite. L’élimination d’une moitié n’est alors plus justifiée et l’algorithme peut conclure à tort que la valeur est absente.

13.2.3 Bornes de la zone de recherche

La version présentée utilise un intervalle fermé : les indices gauche et droite appartiennent tous les deux à la zone encore possible. Au départ, gauche = 0 et droite = n - 1. La zone est vide lorsque gauche > droite.

Il existe aussi des formulations utilisant un intervalle semi-ouvert [gauche, droite[. Elles sont correctes si les conditions et mises à jour restent cohérentes. Mélanger les deux conventions produit fréquemment des erreurs.

13.2.4 Calcul de l’indice du milieu

Avec des indices entiers, le milieu est calculé par division entière. La formule simple est : milieu ← (gauche + droite) DIV 2.

Formule recommandée dans les langages à entiers bornés

Cette seconde écriture évite que l’addition gauche + droite dépasse la valeur maximale du type entier lorsque les indices sont très grands. Dans le cadre des exercices, les deux formules donnent le même indice.

13.2.5 Mise à jour des bornes

Après une comparaison infructueuse, l’élément du milieu est exclu de la nouvelle zone, puisqu’il vient d’être vérifié. Il faut donc utiliser milieu - 1 ou milieu + 1. Réutiliser milieu sans le dépasser peut empêcher la zone de diminuer et provoquer une boucle infinie.

Règles de mise à jour

13.2.6 Version itérative

Recherche dichotomique itérative

Le retour immédiat simplifie la lecture : dès que l’égalité est rencontrée, aucune autre comparaison n’est nécessaire. Si la boucle se termine, la zone est vide et la valeur est absente.

13.2.7 Traçage d’une recherche réussie

Considérons le tableau trié T = [3, 6, 9, 12, 15, 18, 21, 24, 27] et la recherche de x = 21.

Seules deux comparaisons principales sont nécessaires, alors qu’une recherche séquentielle depuis le début aurait examiné sept éléments.

13.2.8 Traçage d’une recherche infructueuse

Recherchons maintenant x = 20 dans le même tableau.

L’intervalle devient vide sans que toutes les cases soient examinées. L’ordre du tableau permet de conclure que 20 ne peut se trouver ailleurs.

13.2.9 Version récursive

La version récursive reçoit les bornes de la zone courante. Son cas de base d’échec correspond à gauche > droite. Chaque appel réduit la taille de l’intervalle.

Recherche dichotomique récursive

13.2.10 Tableau contenant des doublons

Une recherche dichotomique classique retourne une occurrence quelconque. Pour trouver la première occurrence, il faut continuer la recherche dans la moitié gauche même après une égalité. Pour trouver la dernière, on continue dans la moitié droite.

Première occurrence par recherche dichotomique

13.2.11 Recherche dans un tableau trié décroissant

La méthode reste applicable à un tableau trié par ordre décroissant, mais les décisions doivent être inversées. Si x est inférieur à T[milieu], il faut chercher à droite, là où se trouvent les valeurs plus petites.

Règle pour un ordre décroissant

13.2.12 Erreurs fréquentes

13.3 Comparaison des méthodes

13.3.1 Nombre d’opérations

L’opération principale est la comparaison entre la clé et un élément du tableau. Le nombre de comparaisons dépend de la position de la valeur, de son absence éventuelle et de la méthode utilisée.

La notation O(n) pour la recherche séquentielle et O(log n) pour la recherche dichotomique sera approfondie dans le chapitre consacré à la complexité. À ce stade, il suffit de retenir que doubler la taille double approximativement le pire travail séquentiel, tandis qu’il ajoute environ une étape à la recherche dichotomique.

13.3.2 Influence de la taille des données

Pour un très petit tableau, la simplicité de la recherche séquentielle peut être suffisante. Lorsque le nombre d’éléments devient important et que le tableau est déjà trié, la recherche dichotomique réduit fortement le nombre de comparaisons.

La taille ne doit toutefois pas être considérée seule. Le coût de préparation des données, leur fréquence de modification et le nombre de recherches prévues influencent le choix.

13.3.3 Tableau trié ou non trié

13.3.4 Cas favorable et cas défavorable

Le cas moyen dépend de la distribution des recherches et de la probabilité que chaque élément soit demandé. Dans un tableau non trié où toutes les positions sont aussi probables, une recherche séquentielle réussie examine en moyenne environ la moitié des éléments.

13.3.5 Mémoire utilisée

Les versions itératives utilisent seulement quelques variables supplémentaires : un indice pour la recherche séquentielle et trois indices pour la recherche dichotomique. Leur mémoire auxiliaire reste donc constante.

Les versions récursives créent une pile d’appels. Une recherche séquentielle récursive peut empiler jusqu’à n appels, tandis qu’une recherche dichotomique récursive n’en empile qu’un nombre proportionnel au nombre de divisions successives.

13.3.6 Coût global : trier puis rechercher

La recherche dichotomique ne doit pas être évaluée isolément lorsque les données sont initialement non triées. Il faut aussi considérer le coût du tri. Pour une seule recherche, trier tout le tableau peut être inutile. Pour des centaines de recherches sur les mêmes données, le tri initial peut être amorti.

13.3.7 Tableau de décision

Applications guidées

Application 1 — Rechercher un étudiant par matricule

Un tableau Matricules contient les identifiants des étudiants dans l’ordre d’inscription, sans garantie de tri. Concevoir une fonction qui retourne l’indice d’un matricule demandé.

Solution adaptée

La recherche séquentielle est choisie parce que le tableau n’est pas garanti trié.

Application 2 — Rechercher une note dans une liste triée

Les notes ont été classées par ordre croissant. On souhaite déterminer rapidement si la note 14,5 est présente.

Solution adaptée

La recherche dichotomique est pertinente, car l’ordre est connu et permet d’éliminer une moitié à chaque étape.

Application 3 — Compter les absences

Un tableau de caractères contient P pour présent et A pour absent. Il faut compter toutes les absences. Un arrêt à la première occurrence serait incorrect.

Parcours complet

Application 4 — Première et dernière occurrence

Dans T = [1, 2, 2, 2, 2, 5, 9], déterminer les indices de la première et de la dernière occurrence de 2. Deux recherches dichotomiques modifiées permettent d’obtenir les bornes du bloc de doublons.

Dernière occurrence

La première occurrence vaut 1 et la dernière vaut 4. Le nombre d’occurrences est donc 4 - 1 + 1 = 4.

Application 5 — Point d’insertion dans un tableau trié

Même lorsque x est absent, la dichotomie peut déterminer l’indice où x devrait être inséré afin de préserver l’ordre. À la fin de la boucle, la borne gauche indique cette position.

Indice d’insertion

Méthode de résolution et de traçage

Méthode pour une recherche séquentielle

1.  Préciser le résultat demandé : existence, position, compteur ou toutes les positions.

2.  Déterminer si un arrêt anticipé est autorisé.

3.  Initialiser l’indice et les éventuels compteurs.

4.  Contrôler la borne avant chaque accès au tableau.

5.  Comparer l’élément courant à la clé.

6.  Mettre à jour l’indice ou le résultat.

7.  Traiter clairement le cas où la valeur est absente.

Méthode pour une recherche dichotomique

1.  Vérifier que le tableau est trié et connaître le sens du tri.

2.  Choisir une convention d’intervalle et la conserver.

3.  Initialiser gauche et droite.

4.  Calculer le milieu par division entière.

5.  Comparer la clé à l’élément central.

6.  Exclure le milieu et conserver une seule moitié.

7.  Répéter tant que la zone n’est pas vide.

8.  Tester les cas à zéro, un et deux éléments.

Erreurs fréquentes et bonnes pratiques

Travaux dirigés

Pour chaque exercice, préciser les préconditions, le résultat retourné, le pseudo-code et au moins quatre jeux d’essai incluant un cas limite.

Exercice 1 — Présence et position

Écrire deux fonctions de recherche séquentielle dans un tableau d’entiers : la première retourne un booléen indiquant si x existe ; la seconde retourne l’indice de sa première occurrence ou -1.

Exercice 2 — Dernière occurrence séquentielle

Écrire une fonction qui retourne la dernière occurrence de x dans un tableau non trié. Proposer une version parcourant le tableau de gauche à droite, puis une version partant de la fin.

Exercice 3 — Toutes les positions

Construire un tableau P contenant les indices de toutes les occurrences de x dans T. La fonction retourne le nombre d’indices écrits dans P.

Exercice 4 — Recherche parmi des noms

Un tableau contient des noms. Écrire une recherche qui ne distingue pas les majuscules des minuscules. Exemple : « AMAL » et « Amal » doivent être considérés comme égaux.

Exercice 5 — Trace dichotomique

Tracer la recherche des valeurs 4, 26 et 17 dans le tableau trié [2, 4, 7, 11, 15, 18, 21, 26, 30]. Indiquer gauche, droite, milieu et décision à chaque étape.

Exercice 6 — Corriger les bornes

L’algorithme suivant contient plusieurs erreurs. Les identifier et proposer une version correcte.

Exercice 7 — Première occurrence dichotomique

Écrire et tracer une fonction qui retourne la première occurrence de x dans un tableau trié contenant des doublons.

Exercice 8 — Nombre d’occurrences par deux recherches

Dans un tableau trié, calculer le nombre d’occurrences de x à partir de sa première et de sa dernière occurrence. Éviter un parcours complet du bloc de doublons.

Exercice 9 — Comparaison expérimentale

Pour des tableaux de tailles 8, 16, 32 et 64, compter les comparaisons réalisées par les deux méthodes lorsque la valeur est absente. Présenter les résultats dans un tableau et commenter leur évolution.

Exercice 10 — Choix de méthode

Choisir et justifier une méthode pour chacune des situations suivantes : une liste non triée de 20 noms ; un annuaire trié de 100 000 noms ; une seule recherche dans un fichier non trié ; 10 000 recherches dans une liste stable ; comptage de toutes les valeurs égales à 0.

Corrigés indicatifs

Corrigé 1 — Présence et position

Corrigé 2 — Dernière occurrence séquentielle

Version depuis la fin

Lorsque la valeur est absente, i devient -1. Le parcours depuis la fin permet un arrêt dès que la dernière occurrence est rencontrée.

Corrigé 3 — Toutes les positions

Corrigé 4 — Recherche parmi des noms

Dans une application réelle, il est souvent préférable de normaliser les noms une seule fois au moment du stockage plutôt qu’à chaque comparaison.

Corrigé 5 — Trace dichotomique

Corrigé 6 — Corriger les bornes

Les erreurs sont : droite initialisée à n au lieu de n - 1, condition gauche < droite qui peut ignorer la dernière case et mises à jour qui peuvent conserver le milieu.

Version corrigée

Corrigé 7 — Première occurrence dichotomique

Corrigé 8 — Nombre d’occurrences

La formule est valable parce que les occurrences d’une même valeur sont contiguës dans un tableau trié.

Corrigé 9 — Comparaison expérimentale

Quand n double, le pire cas séquentiel double. Pour la dichotomie, une seule étape supplémentaire suffit approximativement.

Corrigé 10 — Choix de méthode

Synthèse du chapitre

La recherche séquentielle est universelle et simple : elle examine les éléments dans leur ordre de stockage. Elle est adaptée aux données non triées, aux petits tableaux et aux traitements qui nécessitent toutes les occurrences. La recherche dichotomique est beaucoup plus rapide sur les grandes données triées, car elle divise la zone possible par deux à chaque étape.

Checklist de conception

1.  Définir précisément ce que doit retourner la recherche.

2.  Identifier la taille utile du tableau et valider les bornes.

3.  Vérifier si l’ordre des données est garanti.

4.  Choisir entre parcours complet et arrêt anticipé.

5.  Traiter explicitement le tableau vide et la valeur absente.

6.  Pour la dichotomie, fixer une convention d’intervalle.

7.  Exclure le milieu après chaque comparaison infructueuse.

8.  Tester une zone de un puis de deux éléments.

9.  Traiter les doublons selon le besoin.

10.  Comparer le coût global, y compris un éventuel tri préalable.

Glossaire

Auto-évaluation