Introduction
Tu es tombé sur un groupe de mathématiciens qui sont aussi auteurs-compositeurs-interprètes.
Ils ont écrit une chanson pour chacun de leurs nombres préférés et, comme tu peux l'imaginer, ils ont beaucoup de nombres préférés (comme 0, 73 ou 6174).
Tu es curieux d'entendre la chanson de ton nombre préféré, mais avec autant de chansons à parcourir, trouver la bonne pourrait prendre un certain temps.
Heureusement, ils ont organisé leurs chansons dans une liste de lecture triée par titre, qui n'est autre que le nombre dont parle la chanson.
Tu réalises que tu peux utiliser un algorithme de recherche dichotomique pour trouver rapidement une chanson à partir de son titre.
Instructions
Ta tâche consiste à implémenter un algorithme de recherche dichotomique.
Un algorithme de recherche dichotomique permet de trouver un élément dans un tableau en le divisant en deux à plusieurs reprises, et en ne conservant que la moitié qui contient l'élément recherché.
Il permet de réduire rapidement les emplacements possibles de cet élément jusqu'à ce qu'on le trouve, ou jusqu'à ce qu'on ait éliminé tous les emplacements possibles.
La recherche dichotomique ne fonctionne que si le tableau a été trié.
L'algorithme se présente comme ceci :
- Trouver l'élément du milieu d'un tableau trié et le comparer avec l'élément recherché.
- Si l'élément du milieu est l'élément recherché, c'est terminé !
- Si l'élément du milieu est supérieur à l'élément recherché, éliminer cet élément et tous ceux qui se trouvent après lui.
- Si l'élément du milieu est inférieur à l'élément recherché, éliminer cet élément et tous ceux qui se trouvent avant lui.
- Si tous les éléments du tableau ont été éliminés, alors l'élément ne se trouve pas dans le tableau.
- Sinon, répéter le processus sur la partie du tableau qui n'a pas été éliminée.
Voici un exemple :
Imaginons que l'on cherche le nombre 23 dans le tableau trié suivant : [4, 8, 12, 16, 23, 28, 32].
- On commence par comparer 23 avec l'élément du milieu, 16.
- Comme 23 est supérieur à 16, on peut éliminer la moitié gauche du tableau, ce qui nous laisse
[23, 28, 32].
- On compare ensuite 23 avec le nouvel élément du milieu, 28.
- Comme 23 est inférieur à 28, on peut éliminer la moitié droite du tableau :
[23].
- On a trouvé l'élément recherché.
