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.
Messages d'exception
Il est parfois nécessaire de lever une exception. Lorsque tu fais cela, tu dois toujours inclure un message d'erreur explicite pour indiquer quelle est la source de l'erreur. Cela rend le code plus lisible et facilite grandement le débogage. Dans les cas où tu sais que la source de l'erreur sera d'un certain type, tu peux choisir de lever l'un des types d'erreur intégrés, mais tu dois quand même inclure un message explicite.
Cet exercice particulier exige que tu utilises l'instruction raise pour « lever » une ValueError lorsque la valeur donnée ne se trouve pas dans le tableau. Les tests ne réussiront que si tu lèves l'exception avec raise et que tu y ajoutes un message.
Pour lever une ValueError avec un message, écris le message comme argument du type exception :
# example when value is not found in the array.
raise ValueError("value not in array")
