Les algorithmes de recherche
Instinctivement, lorsqu’on souhaite rechercher quelques choses, on utilise des hypothèses pour trouver ce que l’on cherche plus rapidement. Par exemple, lorsqu’on a perdu ses clés, on cherche en premier sur la table, sur le bureau… C’est seulement après avoir cherché dans tous les endroits probables, on commence à chercher dans les plus improbables : le frigo. En d’autres termes, vous avez appliqué un algorithme de recherche.
Quand on effectue une recherche dans un tableau, il faut procéder itérativement sur chacune des valeurs de ce tableau. Ce procédé est appelé la recherche linéaire. Les algorithmes de recherches doivent toujours tenir compte du contexte. Dans un tableau, ce contexte correspond à s’il est trié ou non. C’est-à-dire que si vous recherchez une valeur dans un tableau trié, il est inutile de poursuivre la recherche si les valeurs du tableau sont en dehors du domaine de recherche. Par exemple, lorsqu’on recherche la valeur 5 dans le tableau croisant [1, 4, 7, 9], vous pouvez interrompre prématurément la recherche à la valeur 7, puisqu’elle est plus grande que votre nombre.
Il est possible d’être beaucoup plus efficace lorsqu’on effectue la recherche d’un élément dans un tableau trié. Cet algorithme est celui que l’on emploie naturellement quand on recherche un mot dans le dictionnaire. On ouvre le dictionnaire au milieu, et on regarde si le mot se situe avant ou après la page que l’on a ouverte. De cette façon, la taille de la recherche dans le dictionnaire est ainsi divisée par deux puisqu’il est possible d’ignorer une partie des mots. On continue notre recherche en ouvrant une page parmi l’ensemble des pages restantes. On répète ainsi l’opération jusqu’à trouver le mot. Cet algorithme est appelé la recherche dichotomique.
