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 string& s, 
                      int a, int b, 
                      const data t[]) {
  // recherche dans t[a],...,t[b] 
  if (a<=b) {
    int m = (a+b)/2;

    if (s == t[m].key) {
      return t[m];
    } else if (s < t[m].key) {
      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 string& 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;
    if (s == t[m].key) {
      return table[m];
    } else if (s < t[m].key) {
      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 >>.