Accueil › Coding & algorithmique › Où insérer sans casser l'ordre
Où insérer sans casser l'ordre
Exercice de la série « Tri, recherche et collecteurs »intermediaire
Le problème. Un barème de seuils trié par ordre croissant. Pour une valeur donnée, on veut la position du premier seuil supérieur ou égal à cette valeur — c'est-à-dire l'endroit où l'insérer sans défaire le tri. Si tous les seuils sont inférieurs, la position est la fin du tableau.
Écrivez borneInferieure(seuils, valeur).
| Appel | Résultat attendu |
|---|---|
borneInferieure([1, 3, 5, 7], 5) |
2 |
borneInferieure([1, 3, 5, 7], 4) |
2 — 4 s'insère avant 5 |
borneInferieure([1, 3, 5, 7], 0) |
0 |
borneInferieure([1, 3, 5, 7], 9) |
4 — après le dernier |
borneInferieure([2, 2, 2], 2) |
0 — la première position |
borneInferieure([], 1) |
0 |
Ce qu'on attend. O(log n). La recherche d'égalité stricte ne répond
pas à cette question : elle rend -1 dès que la valeur est absente,
alors qu'ici l'absence a une réponse utile.
Le piège. L'invariant. Avec des doublons, il faut la première position qui convient, pas n'importe laquelle.
Cas de test
[[1,3,5,7],5][[1,3,5,7],4][[1,3,5,7],0][[1,3,5,7],9][[2,2,2],2][[],1]
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.