Rechercher un élément dans un tableau trié

L'objectif de cet exercice est d'écrire une fonction indice

• qui prend en argument :
  • un tableau valeurs rangé dans l'ordre croissant
  • une valeur cible
• qui renvoie :
  • l'indice de cible dans le tableau s'il en fait partie
  • None sinon

La fonction indice utilisera une fonction indice_recursive qui sera récursive et qui prendra les mêmes arguments que indice, et en plus debut et fin qui désigneront les indices pour la recherche : de debut inclus à fin inclus.

Le tableau valeurs pourra être rempli d'entiers ou rempli de chaines de caractères, sans aucun changement à procéder ; en effet ce sont des éléments comparables entre eux, ordre naturel pour les entiers, ordre lexicographique pour les chaines de caractères.

Exemples

🐍 Console Python

>>> nombres = [2, 3, 5, 7, 11, 13, 17]
>>> indice(nombres, 7)
3
>>> indice(nombres, 8) is None
True

🐍 Console Python

>>> fruits = ["abricot", "kiwi", "mangue", "poire", "pomme"]
>>> fruits == sorted(fruits)  # le tableau est bien trié
True
>>> indice(fruits, "kiwi")
1
>>> indice(fruits, "cerise") is None
True

Compléter le code ci-dessous

###

Lancer # Testsbksl-nlbksl-nl#1bksl-nlnombres = [2, 3, 5, 7, 11, 13, 17]bksl-nlassert indice(nombres, 7) == 3bksl-nlassert indice(nombres, 8) is Nonebksl-nlbksl-nlbksl-nl#2bksl-nlbksl-nlfruits = ["abricot", "kiwi", "mangue", "poire", "pomme"]bksl-nlassert fruits == sorted(fruits) # le tableau est bien triébksl-nlassert indice(fruits, "kiwi") == 1bksl-nlassert indice(fruits, "cerise") is Nonebksl-nlbksl-nlbksl-nl# Autres testsbksl-nlbksl-nlnombres = [42]bksl-nlassert indice(nombres, 42) == 0bksl-nlassert indice(nombres, 1337) is Nonebksl-nlbksl-nlbksl-nlvaleurs = [2py-stri for i in range(8)]bksl-nlfor i in range(8):bksl-nl cible = 2py-stribksl-nl attendu = ibksl-nl assert indice(valeurs, cible) == attendu, f"Erreur avec {cible} dans {valeurs}"bksl-nlfor i in range(9):bksl-nl cible = 2py-stri - 1bksl-nl assert indice(valeurs, cible) is None, f"Erreur avec {cible} dans {valeurs}"bksl-nlbksl-nltxt = [chr(ord('A') + i) for i in range(26)]bksl-nlfor i in range(26):bksl-nl cible = chr(ord('A') + i)bksl-nl attendu = ibksl-nl assert indice(txt, cible) == attendu, f"1.Erreur avec {cible} dans {txt}"bksl-nl cible = chr(ord('A') + i) + "!"bksl-nl assert indice(txt, cible) is None, f"2.Erreur avec {cible} dans {txt}"bksl-nl cible = "!" + chr(ord('A') + i)bksl-nl assert indice(txt, cible) is None, f"3.Erreur avec {cible} dans {txt}"bksl-nlcible = ""bksl-nlassert indice(txt, cible) is None, f"4.Erreur avec {cible} dans {txt}"bksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def indicepy-undrecursive(valeurs, cible, debut, fin):bksl-nl if debut > fin:bksl-nl return Nonebksl-nl milieu = (debut + fin) // ...bksl-nl if valeurs[milieu] > ...:bksl-nl return indicepy-undrecursive(valeurs, cible, ..., ...)bksl-nl elif ...:bksl-nl return indicepy-undrecursive(valeurs, cible, ..., ...)bksl-nl else:bksl-nl return milieubksl-nlbksl-nldef indice(valeurs, cible):bksl-nl return ...(valeurs, cible, 0, len(valeurs) - 1)bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl#1bksl-nlnombres = [2, 3, 5, 7, 11, 13, 17]bksl-nlassert indice(nombres, 7) == 3bksl-nlassert indice(nombres, 8) is Nonebksl-nlbksl-nlbksl-nl#2bksl-nlbksl-nlfruits = ["abricot", "kiwi", "mangue", "poire", "pomme"]bksl-nlassert fruits == sorted(fruits) # le tableau est bien triébksl-nlassert indice(fruits, "kiwi") == 1bksl-nlassert indice(fruits, "cerise") is Nonebksl-nlbksl-nldef indicepy-undrecursive(valeurs, cible, debut, fin):bksl-nl if debut > fin:bksl-nl return Nonebksl-nl milieu = (debut + fin) // 2bksl-nl if valeurs[milieu] > cible:bksl-nl return indicepy-undrecursive(valeurs, cible, debut, milieu - 1)bksl-nl elif valeurs[milieu] < cible:bksl-nl return indicepy-undrecursive(valeurs, cible, milieu + 1, fin)bksl-nl else:bksl-nl return milieubksl-nlbksl-nlbksl-nldef indice(valeurs, cible):bksl-nl return indicepy-undrecursive(valeurs, cible, 0, len(valeurs) - 1)bksl-nlbksl-nlbksl-nlbksl-nl

---

---