7. Les recherches

La recherche est une opération fondamentale dans un programme qui gère un ensemble de données. Elle participe souvent à l’élaboration des autres traitements, par exemple en localisant la donnée à afficher ou à modifier. La recherche traite deux informations distinctes, la clef et la donnée. La clef est l’information utilisée dans la recherche pour localiser la donnée. C’est par exemple le nom de l’employé qui permet de trouver l’ensemble des informations qui le concernent. La clef est alors un élément (le champ nom) de la donnée (l’employé).
La recherche séquentielle est une méthode élémentaire qui consiste à comparer la clef recherchée à toutes les autres clefs. Sa complexité algorithmique est en O(N). Rechercher une valeur entière dans une liste d’entiers se résume à parcourir chaque élément de la liste, et à vérifier s’il s’agit de l’élément recherché. Dans cet exemple, la clef et la donnée sont confondues. La boucle utilisée dans une recherche séquentielle est une boucle TANT QUE avec un double critère d’arrêt : on s’arrête quand on a trouvé la donnée ou quand on atteint la fin de la liste. Voici la fonction recherchant une valeur dans une liste de valeurs entières contenues dans un tableau. Les paramètres sont le tableau des données (tab), le nombre d’éléments dans le tableau (nb) et la valeur recherchée (valrech). Cette fonction retourne le numéro de la case du tableau dans laquelle se trouve la donnée, ou –1 (représenté par la constante non_trouvé) si elle n’est pas trouvée…