13.2. Recherche séquentielle

Quand on a un tableau T formé de paires :

(K₁,I₁) (K₂,I₂) ..... (K_n,I_n)

et une valeur K qu'il faut rechercher dans le tableau, on peut envisager la méthode la plus simple qui soit : la recherche séquentielle.

1. initialisation : i 1
2. si i = n+1 alors pas trouvé (échec)
3. si clé (T[i]) = K alors trouvé (succès)
4. si ni 2 ni 3 applicables, continuer la recherche : i i+1 et retour en 2.

Cette méthode est la plus simple mais aussi la plus inefficace car elle comporte deux tests à chaque itération. On peut l'améliorer de la manière suivante :

1. initialisation clé(T[0]) K, i n
2. trouvé ? si clé(T[i]) = K alors aller à 3 sinon i i-1 et répéter 2
3. fin. Si i = 0 alors pas trouvé sinon trouvé

Cette version présente une amélioration (un seul test par itération) qui se traduit par un temps d'exécution réduit de 20 % en moyenne (un test de moins à évaluer).

Autre amélioration : la recherche séquentielle peut être grandement améliorée si l'on range, dans le tableau, les composantes dans l'ordre de fréquence de recherche, c'est-à-dire en mettant dans les premières places les composantes les plus fréquemment recherchées.

13.3 Recherche dans un tableau ordonné

Table des matières.

Site Hosting: Bronco