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 l'usage préalable d'un algorithme de tri. On peut alors réaliser un test avec trois résultats : égalité, inférieur, supérieur. On suppose ici que le type de la clé permet ce tri, ce qui est le cas du type String, comme de tout sous-type de l'interface Comparable dont les instances sont mutuellement comparables.

L'algorithme de recherche séquentielle peut tirer parti de cet ordre en interrompant la recherche dès qu'une clé strictement supérieure à la clé cherchée est rencontrée. Ceci réduit le coût d'une recherche en cas d'échec : au maximum, N, et en moyenne N/2. Cette amélioration n'est pas significative.

La bonne idée est de comparer la clé recherchée avec la clé du milieu du tableau ; si la clé recherchée est plus petite, on continue la recherche dans la première moitié du tableau ; si elle est plus grande, on continue dans la seconde moitié du tableau. On suppose ici, pour simplifier, qu'aucune suppression n'a été effectuée, de sorte qu'il n'y a pas de valeurs nulles dans le tableau. La formulation récursive est la plus naturelle :

  Object rechercheDichotomique(Object clé, int a, int b) {
                                       
    // recherche dans t[a],...,t[b]
    if (a<=b) {
      int m = (a+b)/2;
      int c = tableau[m].clé.compareTo(clé);
      if (c == 0) {
        return tableau[m].information;
      } else if (c > 0) {
        return rechercheDichotomique(clé, a, m-1);
      } else {
        return rechercheDichotomique(clé, m+1, b);
      }
    } else {
      return null;
    }
  }

  public Object rechercher(Object clé) {
    return rechercheDichotomique(clé, 0, nbElements-1);
  }

Cette définition récursive terminale se transforme facilement en définition itérative :

  Object rechercheDichotomiqueIter(Object clé, int a, int b) {
                                            
    // recherche dans t[a],...,t[b]
    while (a<=b) {
      int m = (a+b)/2;
      int c = tableau[m].clé.compareTo(clé);
      if (c == 0) {
        return tableau[m].information;
      } else if (c > 0) {
        b = m-1;
      } else {
        a = m+1;
      }
    }
  return null;
  }

La recherche dichotomique dans une table de taille N nécessite au plus $\log_2 N$ comparaisons. Cette réduction logarithmique de la complexité est un premier exemple de la méthode << diviser pour régner >>. Cependant, l'insertion dans un tableau ordonné se fait en un temps linéaire (il faut $\log_2 N$ comparaisons pour trouver la position de l'élément à insérer, plus une moyenne de N/2 décalages vers la droite des éléments de la table plus grands que l'élément inséré). Cette implémentation n'est avantageuse que si les insertions sont plus rares que les recherches. L'insertion est plus facile si l'on remplace le tableau par une liste chaînée : elle se ferait en temps constant une fois la position trouvée.