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 trouve un élément dans un tableau en le coupant en deux à plusieurs reprises, et en ne gardant que la moitié qui contient l'élément recherché.
Il permet de réduire rapidement les emplacements possibles de notre é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 fonctionne comme ceci :
- Trouve l'élément du milieu d'un tableau trié et compare-le à l'élément recherché.
- Si l'élément du milieu est notre élément, alors c'est fini !
- Si l'élément du milieu est plus grand que notre élément, on peut éliminer cet élément ainsi que tous les éléments qui se trouvent après lui.
- Si l'élément du milieu est plus petit que notre élément, on peut éliminer cet élément ainsi que tous les éléments qui se trouvent avant lui.
- Si tous les éléments du tableau ont été éliminés, alors l'élément n'est pas dans le tableau.
- Sinon, on répète le processus sur la partie du tableau qui n'a pas été éliminée.
Voici un exemple :
Imaginons qu'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 plus grand que 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 plus petit que 28, on peut éliminer la moitié droite du tableau :
[23].
- On a trouvé notre élément.
Conseils
Haskell prend en charge de nombreux types de tableaux. Cet exercice utilise des tableaux immuables, boxed et non-strict de Data.Array. Pour en savoir plus sur l'utilisation de ces tableaux, consulte :
Comme prolongement facultatif de cet exercice, essaie de faire fonctionner la fonction find avec des tableaux aux bornes arbitraires, par exemple des tableaux dont le premier indice n'est pas forcément 0.
