Recherche binaire

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.

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.

Comportement

Ta solution doit reproduire le comportement des fonctions searchsorted intégrées à Julia pour les cas de test. Cela signifie qu'au lieu de renvoyer l'indice du premier élément correspondant que tu trouves dans le tableau, tu renverras une plage dont la borne inférieure est l'indice du premier élément correspondant dans le tableau et dont la borne supérieure est l'indice du dernier élément correspondant dans le tableau. Toutefois, pour simplifier ta solution, tu peux supposer que l'élément cible n'est pas répété, sauf pour le jeu de tests bonus sur les correspondances multiples.

Si l'élément recherché ne se trouve pas dans le tableau, tu dois renvoyer une plage vide dont la borne inférieure est l'indice auquel l'élément pourrait être inséré dans le tableau trié. Une plage vide est une plage dont la borne supérieure est inférieure à la borne inférieure.

Lis la documentation et les exemples de la fonction searchsorted pour plus de détails :

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

Tâches bonus

• Étends ta solution pour prendre en charge les arguments nommés by, lt et rev, de sorte que by désigne une transformation appliquée à tous les éléments du tableau, lt une comparaison et rev indique si le tableau est trié en ordre inverse. Quand ces paramètres sont utilisés, tu dois supposer que le tableau a déjà été trié selon ces paramètres. Consulte la documentation de sort pour plus de détails.
• Prends en charge les tableaux où l'élément cible est répété (trouve le premier et le dernier indice où l'élément est égal à l'élément cible).

---

Source

Wikipedia