二进制搜索以找到排序列表中小于特定值的最后一个元素 [英] Binary search to find last element in sorted list that is less then specific value

问题描述

我正在搜索一个消息字典，该字典包含unixtimes，长度为N，我想在该字典中查找任意24小时(86400秒)时隙内的最大消息数(我将此称为频率).这意味着，如果有五个消息在一个消息的24小时内具有unixtime，我想要5个消息.

I am searching through a dictionary of messages, that contain unixtimes, with length N, where I want to find maximum number of messages (I call this the frequency) that is inside an arbitrary 24 hour (86400 seconds) time slot. That means that if there are five messages with an unixtime within 24 hours of one I want 5.

我想通过二进制搜索来完成此任务，但是我在如何最好地实现以及是否可以使用某些二进制搜索库方面有些疯狂.

I want to accomplish this with binary search, but I am a little bit in the wild on how I can implement that as best, and if I can use some binarysearch library.

这是我使用10个元素的搜索网格来完成的操作:

This is how I do it with a search grid of 10 elements:

        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整除时，这是不好的

I think I've screwed up this one as well, but I cannot find out how - I know it is no good when the length of AISmessages isnt divisible by 10 f.ex

我如何将其标准化为二进制搜索，从而使我能够在字典中具有任意数量的元素的24小时时隙内查看消息的频率?

How would I standarize this to a binary search that gives me the frequency of the messages inside a 24 hour timeslot in a dictionary with any number of elements?

推荐答案

您可以使用 <标准库中的c0> .我不确定我是否正确理解了您的问题，但是解决方案可能看起来像这样:

You can use bisect from the standard library. I'm not sure if I understood your problem correctly, but a solution may look something like this:

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

---

示例:这将为您提供列表a中的项目数，其值的范围为30，从带有索引2的条目开始(假定对a进行了排序):

---

Example: This gives you the number of items in the list a with values in a range of 30, starting from the entry with index 2 (assuming a is sorted):

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

这篇关于二进制搜索以找到排序列表中小于特定值的最后一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！