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.
Restrictions
Ne prends pas la facilité en utilisant la bibliothèque standard d'outils de collection. Tu peux et tu dois faire cet exercice sans des outils comme Array.tryFindIndex.
Astuces
Pour cet exercice, les fonctionnalités F# suivantes te seront utiles :
-
La récursion terminale évite les débordements de pile sur des entrées volumineuses grâce à la récursion terminale. Même si aucun cas de test ne le vérifie explicitement, la récursion terminale conduit à une solution plus performante. Une autre bonne ressource sur la récursion terminale est cet article de blog.
-
La correspondance de motifs est extrêmement puissante et aide à simplifier la logique conditionnelle à plusieurs branches.
