Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Toutes les occurrences, en O(log n)

Toutes les occurrences, en O(log n)

Exercice de la série « Tri, recherche et collecteurs »avance

Le problème. Un journal d'événements horodatés, trié. Pour un horodatage donné, on veut l'intervalle des positions qu'il occupe : première et dernière.

Écrivez intervalle(journal, valeur) qui renvoie [premiere, derniere], ou [-1, -1] si la valeur est absente.

Appel Résultat attendu
intervalle([1, 2, 2, 2, 3], 2) [1, 3]
intervalle([1, 2, 3], 4) [-1, -1]
intervalle([2, 2], 2) [0, 1]
intervalle([1], 1) [0, 0]
intervalle([], 1) [-1, -1]

Ce qu'on attend. O(log n). Trouver une occurrence puis élargir linéairement redonne du O(n) dès que la valeur est très répétée — ce qui est précisément le cas intéressant.

L'indication. Deux recherches de borne suffisent, et la seconde se déduit de la première sans écrire un second algorithme.

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Tri, recherche et collecteurs »