Prépa Code Connexion Inscription

Écrire une fonction indice_insertion(lst, x) qui renvoie l'indice auquel insérer x dans la liste triée lst (par ordre croissant) pour que la liste reste triée.

S'il existe déjà des éléments égaux à x, on insère x avant ces éléments : c'est-à-dire qu'on renvoie l'indice du premier élément supérieur ou égal à x. Si x est strictement plus grand que tous les éléments, on renvoie len(lst).

On attend une implémentation en O(log n) par dichotomie.