La première occurrence
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 5 — Algorithmes dichotomiques
Énoncé
En présence de doublons dans un tableau trié, l'algorithme classique renvoie un indice quelconque. Écrire premiere_occurrence(v, t) renvoyant le plus petit indice tel que t[i] == v (ou None), en temps .
Corrigé
Lorsqu'on trouve un élément égal à , on continue la recherche dans la moitié gauche du tableau (indices plus petits) tout en gardant en mémoire l'indice courant comme meilleure solution temporaire :
def premiere_occurrence(v, t: list):
g, d = 0, len(t) - 1
meilleur = None
while g <= d:
m = (g + d) // 2
if t[m] == v:
meilleur = m
d = m - 1 # Recherche à gauche pour un plus petit indice
elif t[m] < v:
g = m + 1
else:
d = m - 1
return meilleurLes autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.