如何在Python中查找特定日期所在的日期的排序列表？

Question

我有一个排序的日期列表,我正在寻找一种方法来查找输入日期在该排序列表中的位置,但更具体地说是它的上限.

例如,如果在排序日期列表中定位它[0, 1, 2, 3, 4, 5],然后输入日期在位置3和4之间,我希望函数将位置4返回给我.

我可以使用预先制作的二分搜索等吗？或者我必须自己写吗？

Answer 1

您可以使用bisect.bisect_left()或bisect.bisect_right()(别名bisect.bisect())来查找插入点.它将使用二进制搜索在大多数log N步骤中找到该点.

区别在于当你给它一个date()在列表本身时会发生什么; bisect_left()将给出等值本身bisect_right()的索引,在它之后给出索引.

演示:

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