二进制搜索以查找排序列表中小于特定值的最后一个元素

Question

我正在搜索包含 unixtimes、长度为 N 的消息字典，我想在其中找到任意 24 小时（86400 秒）时间内的最大消息数（我称之为频率）投币口。这意味着如果在 24 小时内有 5 条带有 unixtime 的消息，我想要 5 条。

我想用二分搜索来完成这个，但我对如何最好地实现它，以及是否可以使用一些二分搜索库有点不知所措。

这就是我使用 10 个元素的搜索网格的方式：

        cur.execute('SELECT unixtime FROM MessageType1 WHERE userID ='+str(userID[index])+' ORDER BY unixtime asc')
        AISmessages = cur.fetchall()
        AISmessages = {index:x[0] for index,x in enumerate(AISmessages)}
for nextMessageIndex in range(messageIndex+1, len(AISmessages),10):
    if  AISmessages[nextMessageIndex] < message+(86400):
    #Count the number of occurences
        frequency += 10
    elif AISmessages[nextMessageIndex-5] < message+(86400):
        if AISmessages[nextMessageIndex-2] < message+(86400):
            if AISmessages[nextMessageIndex-1] < message+(86400):
                frequency += 9
            else:
                frequency += 8
        elif AISmessages[nextMessageIndex-3] < message+(86400):
            frequency += 7
        elif AISmessages[nextMessageIndex-4] < message+(86400):
            frequency += 6
        else:
            frequency += 5
    elif AISmessages[nextMessageIndex-7] < message+(86400):
        if AISmessages[nextMessageIndex-6] < mssage+(86400):
            frequency += 4
        else:
            frequency += 3
    elif AISmessages[nextMessageIndex-9] < message+(86400):
        if AISmessages[nextMessageIndex-8]< message+(86400):
            frequency += 2
        else:
            frequency += 1
    else:
        break

我想我也把这个搞砸了，但我不知道是怎么回事 - 我知道当 AISmessages 的长度不能被 10 整除时这不好 f.ex

我如何将其标准化为二分搜索，让我在包含任意数量元素的字典中的 24 小时时间段内找到消息的频率？

Answer 1

您可以使用标准库中的 bisect。我不确定我是否正确理解了您的问题，但解决方案可能如下所示：

frequency = bisect(AISmessages[messageIndex:], message+86400)

示例：这会给出列表 a 中值在 30 范围内的项目数，从索引为 2 的条目开始（假设 a 已排序）：

>>> a = [4, 17, 31, 39, 41, 80, 82, 85, 86, 96]
>>> i = 2
>>> m = a[i] # 31
>>> bisect(a[i:], m+30)
3 # correct: 31, 39, 41

二进制搜索以查找排序列表中小于特定值的最后一个元素

Binary search to find last element in sorted list that is less then specific value

python

binary-search