Recherche dichotomique dans une table ordonnée

      

Un supplément d'information permet souvent de réduire la complexité d'un problème. L'algorithme de recherche séquentielle n'utilisait comme information que le test d'égalité sur les clés, avec deux résultats possibles : égalité, non-égalité. Supposons maintenant que les clés d'une table soient rangées par ordre croissant ; cela a pu être obtenu par un algorithme de tri. On peut alors réaliser un test avec trois résultats : égalité, inférieur, supérieur.

L'idée est de comparer la chaîne recherchée avec la clé du milieu du tableau ; si la chaîne est plus petite, on continue la recherche dans la première partie du tableau ; si elle est plus grande, on continue dans la seconde partie du tableau. La formulation récursive est la plus naturelle :

data dicho_search_rec(const char s[], 
                      int a, int b, 
                      const data t[]) {
  /* recherche dans t[a],...,t[b] */
  if (a<=b) {
    int m = (a+b)/2;
    int ordre = strcmp(s, t[m].key);

    if (ordre == 0) {
      return t[m];
    } else if (ordre < 0) {
      return dicho_search_rec(s, a, m-1, t);
    } else {
      return dicho_search_rec(s, m+1, b, t);
    }
  } else {
    return empty_data;
  }
}

L'appel de cette fonction sur un tableau de taille N est

  search_dicho_rec(s, 0, N-1, table);

Cette définition récursive (terminale) se transforme facilement en définition itérative.

data dicho_search_iter(const char s[], 
                      int n, 
                      const data t[]) {
  /* recherche dans t[a],...,t[b] */
  int a = 0;
  int b = n-1;

  while (a<=b) {
    int m = (a+b)/2;
    int ordre = strcmp(s, t[m].key);
    if (ordre == 0) {
      return table[m];
    } else if (ordre < 0) {
      b = m-1;
    } else {
      a = m+1;
    }
  }
  return empty_data;
}

La recherche dans une table de taille N nécessite au plus $\log_2 (N+1)$ comparaisons. Cette réduction logarithmique de la complexité est un exemple de la méthode << diviser pour régner >>.