13.3 Recherche dans un tableau ordonné

13.3.1. Recherche binaire (ou dichotomique, ou logarithmique)

Le principe de cette méthode est de déterminer dans quelle moitié du tableau ordonné pourrait se trouver la valeur recherchée et de recommencer ce procédé dans la moitié en question jusqu'à ce que la fraction du tableau soit vide ou qu'elle ne contienne que la valeur recherchée.

Soit un tableau T de n composantes (triées) tel que :

clé(T[1]) <clé(T[2]) < ..... < clé(T[n])

Les variables g et d sont des indices désignant les limites gauche et droite de la portion de T dans laquelle se fait la recherche. Ainsi, à n'importe quel moment, la position i de la clé k recherchée est comprise entre g et d : g <I < d.

1. initialisation g 0, d n+1

2. point milieu i (g+d)/2
   x = infimum de x : le plus grand entier qui soit plus petit ou égal à x.

3. si i = g alors pas trouvé (échec).

4. comparaison (à ce point g < i < d) il faut envisager les 3 cas suivants :

   cas 1 : si K < clé(T[i]) alors d i et aller 1 à 2.
   cas 2 : si k = clé(T[i]) alors trouvé (succès).
   cas 3 : si k > clé(T[i]) alors g i et aller à 2.

13.3.2. Recherche par interpolation

Si on recherche un nom commençant par "C" dans un annuaire téléphonique on prend un point de départ proche du début de l'annuaire. Si on recherche un nom commençant par V on prendra un point de départ proche de la fin de l'annuaire.

En généralisant on peut déterminer la distance entre deux valeurs x et y comme étant la valeur absolue de la différence (|x-y|). Il est alors possible, lorsque l'on recherche une clé K entre 2 limites K_inf et K_sup, de diviser l'intervalle [K_inf, K_sup] proportionnellement à |K - K_inf| et |K_sup - K| si l'on suppose que les valeurs possibles sont réparties uniformément dans l'intervalle [K_inf,K_sup].

Dans le cas où la répartition ne serait pas uniforme, ce qui est le cas pour des noms dans un annuaire, on peut utiliser un tableau supplémentaire précisant la répartition. Par exemple, pour le cas de l'annuaire, on pourrait avoir un tableau (indicé par une lettre) de 26 composantes de type entier. La composante correspondant à une certaine lettre indique, dans le tableau principal, l'indice du premier nom dont l'initiale est la lettre en question. Pour rechercher un nom donné, on se base alors sur son initiale pour déterminer à quelle position du tableau des noms l'on commencera la recherche.

13.4 Hash-coding ("transformation de clés")

Table des matières.

Site Hosting: Bronco