Formations — 1 037 leçons en français

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

É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 »