Comment trouver dans une liste triée des dates où une date spécifique se situe entre, en Python?

Question

J'ai une liste triée de dates et je cherche un moyen de trouver où une date d'entrée se trouve dans cette liste triée, mais plus précisément la limite supérieure de celle-ci.

E.g. si dans la liste de date triée positionne [0, 1, 2, 3, 4, 5], et que la date d'entrée est entre les positions 3 et 4, je veux que la fonction me renvoie la position 4.

Y at-il une recherche binaire pré-faite etc Je peux utiliser pour cela? Ou devrais-je l'écrire moi-même?

Answer 1

Vous pouvez utiliser bisect.bisect_left() ou bisect.bisect_right() (aliasé à bisect.bisect()) pour trouver ce point d'insertion. Il trouvera ce point dans la plupart des étapes du journal N, en utilisant une recherche binaire. La différence réside dans ce qui se passe quand vous lui donnez un date() qui se trouve dans la liste elle-même; bisect_left() donnera l'indice de la valeur égale elle-même, bisect_right() donne l'index juste après.

Démo:

>>> import bisect 
>>> list_of_dates = [ 
...  date(2015, 1, 15), date(2015, 2, 1), date(2015, 3, 31), 
...  date(2015, 4, 25), date(2015, 5, 23), date(2015, 6, 11)] 
>>> bisect.bisect(list_of_dates, date(2015, 4, 30)) 
4 
>>> bisect.bisect(list_of_dates, date(2015, 4, 25)) 
4 
>>> bisect.bisect_left(list_of_dates, date(2015, 4, 25)) 
3