On considère dans cet exercice des tableaux non vides contenant des nombres entiers, tous distincts, triés dans l'ordre croissant.
On cherche à déterminer l'indice d'une valeur cible dans ce tableau à l'aide d'une recherche dichotomique dans sa version itérative.
Écrire la fonction indice qui prend en paramètres le tableau de nombres tableau et la valeur cherchée cible.
Si la cible est dans le tableau, la fonction renverra son indice. Dans le cas contraire, la fonction renverra None.
Attention
Les tableaux des tests secrets peuvent être très grands. Une recherche linéaire naïve prendrait trop de temps lors de l'exécution.
Les tests secrets limitent le nombre de lectures dans le tableau à 100. Si votre code accède à plus de 100 valeurs dans le tableau, une erreur sera levée.
tableau = [23, 28, 29, 35, 37]bksl-nlbksl-nl# Testsbksl-nlassert indice(tableau, 23) == 0, "Erreur dans la recherche de 23"bksl-nlassert indice(tableau, 29) == 2, "Erreur dans la recherche de 29"bksl-nlassert indice(tableau, 37) == 4, "Erreur dans la recherche de 37"bksl-nlassert indice(tableau, 10) is None, "Erreur dans la recherche de 10"bksl-nlassert indice(tableau, 100) is None, "Erreur dans la recherche de 100"bksl-nlbksl-nl# Tests supplémentairesbksl-nlclass Tableau(list):bksl-nl def py-undpy-undinitpy-undpy-und(self, longueur, fonction):bksl-nl assert longueur > 1py-und000, "La longueur doit être supérieure à 1000"bksl-nl self.py-undlongueur = longueurbksl-nl self.py-undfonction = fonctionbksl-nl self.py-undcompteurpy-undlectures = 0bksl-nl self.py-undlecturespy-undmax = 100bksl-nlbksl-nl def py-undpy-undlenpy-undpy-und(self):bksl-nl return self.py-undlongueurbksl-nlbksl-nl def py-undpy-undgetitempy-undpy-und(self, i):bksl-nl if type(i) is slice:bksl-nl indices = range(py-stri.indices(self.py-undlongueur))bksl-nl return [self.py-undpy-undgetitempy-undpy-und(k) for k in indices]bksl-nl self.py-undcompteurpy-undlectures += 1bksl-nl if self.py-undcompteurpy-undlectures > self.py-undlecturespy-undmax:bksl-nl raise LookupError(f"Il faut réaliser strictement moins de {self.py-undlecturespy-undmax} lectures dans le tableau")bksl-nl return self.py-undfonction(i)bksl-nlbksl-nl def py-undpy-undsetitempy-undpy-und(self, i, x):bksl-nl raise NotImplementedError("Il est interdit de modifier les valeurs")bksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl return f"[{self.py-undfonction(0)}, {self.py-undfonction(1)}, ..., {self.py-undfonction(self.py-undlongueur - 1)}]"bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nl def py-undpy-unditerpy-undpy-und(self):bksl-nl for i in range(self.py-undlongueur):bksl-nl yield self.py-undpy-undgetitempy-undpy-und(i)bksl-nlbksl-nlbksl-nlfrom random import randrangebksl-nlbksl-nlfor test in range(10):bksl-nl # Création du grand tableaubksl-nl exposant = randrange(6, 10)bksl-nl N = 10py-strpy-strexposantbksl-nl a = randrange(2, 50)bksl-nl b = randrange(-1000, 1001)bksl-nl fonction = lambda i: a py-str i + bbksl-nl # Recherche du dernier élémentbksl-nl tableau = Tableau(N, fonction)bksl-nl attendu = N - 1bksl-nl cible = fonction(attendu)bksl-nl assert (bksl-nl indice(tableau, cible) == attendubksl-nl ), f"Erreur lors de la recherche de {cible} dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nl # Recherche d'un élément aléatoirebksl-nl tableau = Tableau(N, fonction)bksl-nl attendu = randrange(0, N - 1)bksl-nl cible = fonction(attendu)bksl-nl assert (bksl-nl indice(tableau, cible) == attendubksl-nl ), f"Erreur lors de la recherche de {cible} dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nlbksl-nl # Recherche d'un élément absentbksl-nl # à gauchebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = fonction(0) - 1bksl-nl assert indice(tableau, cible) is Nonebksl-nl # au centrebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = fonction(randrange(0, N - 1)) + (a - 1)bksl-nl assert indice(tableau, cible) is Nonebksl-nl # à droitebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = tableau[N + 1]bksl-nl assert indice(tableau, cible) is Nonebksl-nlbksl-nlbksl-nlbksl-nl5/5
def indice(tableau, cible):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# Testsbksl-nltableau = [23, 28, 29, 35, 37]bksl-nlassert indice(tableau, 23) == 0, "Erreur dans la recherche de 23"bksl-nlassert indice(tableau, 29) == 2, "Erreur dans la recherche de 29"bksl-nlassert indice(tableau, 37) == 4, "Erreur dans la recherche de 37"bksl-nlassert indice(tableau, 10) is None, "Erreur dans la recherche de 10"bksl-nlassert indice(tableau, 100) is None, "Erreur dans la recherche de 100"bksl-nlbksl-nldef indice(tableau, cible):bksl-nl debut = 0bksl-nl fin = len(tableau) - 1bksl-nl while debut <= fin:bksl-nl milieu = (debut + fin) // 2bksl-nl if cible < tableau[milieu]:bksl-nl fin = milieu - 1bksl-nl elif cible == tableau[milieu]:bksl-nl return milieubksl-nl else:bksl-nl debut = milieu + 1bksl-nl return Nonebksl-nlbksl-nlbksl-nlbksl-nlbksl-nl
Recherche dichotomique itérative : à connaître
Il s'agit de l'algorithme de recherche dichotomique classique.
La recherche de l'indice du milieu
Le calcul de l'indice du milieu mérite toutefois quelques commentaires. Ici on propose milieu=(debut+fin)//2.
Or, dans certains langages de programmation comme le C, la taille des entiers est limitée. Ce calcul milieu=(debut+fin)//2 peut parfois excéder cette taille limite. En effet, si les deux indices debut et fin sont grands, leur somme debut+fin peut dépasser la valeur limite.
Dans ce cas on calcule l'indice du milieu en utilisant la largeur de l'intervalle : milieu=debut+(fin-debut)//2.
Dans le cas présent, le problème ne se pose pas car, en Python, les entiers n'ont pas de taille limite. Toutefois, Si l'on avait manipulé des nombres flottants le problème serait apparu :
Exemple
🐍 Console Python
>>> debut=2.0**1023>>> fin=2.0**1023+1>>> debut+fin# dépassement de capacitéinf>>> (debut+fin)/2# dépassement de capacité lors de la sommeinf>>> debut+(fin-debut)/28.98846567431158e+307