Recherche séquentielle dans une table

L'implémentation la plus simple d'une table se fait à l'aide d'un tableau, et l'algorithme de recherche le plus élémentaire est la recherche séquentielle ; on parcourt le tableau jusqu'à ce qu'un objet de clé donnée soit trouvé ou bien que la fin du tableau soit atteinte et on retourne un objet :

data search(const string& s, int N, const data table[]) {
  int i;

  for (i=0; i<N; i++) {
    if (table[i].key == s) {    // comparaison de deux chaînes
      return table[i];
    }
  }
  return empty_data;            // objet non trouvé 
}

int main()
{
  const int N = 2;
  data table[N] = {{"zero", 0, 0.1}, {"un", 1, 1.1}};
  data d = search("un", N, table);
  cout << d.info2 << endl;     // imprime 1.1
  
  return 0;
}

Cette fonction passe l'objet retourné par valeur, ce qui exige de copier un data qui peut être très volumineux. Pour éviter cette copie, on préfère retourner, non un objet, mais une référence à un objet, de façon analogue à ce qui est fait pour le passage des arguments. Il suffit de remplacer le type de retour data par data&, et ni le corps ni les appels à cette fonction ne doivent être modifiés. La définition devient simplement :

data& search(const string& s, int N, const data table[]) {
  // le corps n'a pas à être modifié
}

On notera que le << return table[i]; >> placé dans la boucle permet de s'en échapper (c'est-à-dire de ne pas exécuter les itérations suivantes) en retournant immédiatement une valeur. Si l'on souhaitait s'échapper de la boucle sans retourner immédiatement, on placerait un << break; >> à la même place. On peut réécrire cette fonction ainsi :

data& search(const string& s, int N, const data table[]) {
  int i;

  for (i=0; i<N; i++) {
    if (table[i].key == s) {
      break;
    }
  if (i<N) {
    return table[i];
  } else {
    return empty_data;
  }
}

La technique bien connue de la sentinelle permet de faire l'économie, à chaque itération, du test i<N, en réservant une position à la fin du tableau, de taille N+1 pour placer la chaîne cherchée :

data& search(const string& s, int N, const data table[]) {
  int i = 0;

  table[N].key = s;              // sentinelle
  while (table[i].key != s) i++;
  return i<N ? table[i] : empty_data;
}

Le nombre maximum de comparaisons effectuées par ce dernier algorithme est de $N$ (quand la clé cherchée n'est pas trouvée) ; en moyenne, il procède à $N/2$ comparaisons. Cela est très mauvais, et on sait faire beaucoup mieux.