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
[[1,2,2,2,3],2][[1,2,3],4][[2,2],2][[1],1][[],1][[2,2,2],2]
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.