Première occurrence par dichotomie
Exercice de TD · niveau 2 · NSI (terminale), chapitre 6 — Diviser pour régner
Énoncé
Première occurrence par dichotomie.
Modifier la recherche dichotomique pour qu'elle renvoie l'indice de la première occurrence d'une valeur présente plusieurs fois dans un tableau trié.
Corrigé
on continue la recherche dans la moitié gauche même après avoir trouvé la cible, en mémorisant la position courante.
def premiere_occurrence(tab, cible):
g, d = 0, len(tab) - 1
res = -1
while g <= d:
m = (g + d) // 2
if tab[m] == cible:
res = m # on memorise et on cherche plus a gauche
d = m - 1
elif tab[m] < cible:
g = m + 1
else:
d = m - 1
return resLes 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.