在Python中，使用二等分查找列表中的项目

问题描述

  test_data = [
 {'offset'： 0，'data'：1500}，
 {'offset'：1270，'data'：120}，
 {'offset'：2117，'data'：30}，
 { 'offset'：4055，'data'：30000}，
] 
  

根据'offset'数据在列表中排序。实际数据可能会更长。

我想要做的是在列表中查找给定一个特定的偏移值的项，这是不

我现在知道Python 模块，这是一个现成的二进制搜索，但不能直接用于这种情况。我只是想知道什么是最简单的方法来适应满足我的需求。这是我想出的：

  import bisect 
 
 class dict_list_index_get_member（object）：
 def __init __（self，dict_list，member）：
 self.dict_list = dict_list 
 self.member = member 
 def __getitem __（self，index）：
 return self.dict_list [index] [self.member] 
 def __len __（self）：
 return self.dict_list .__ len __（）
 
 test_data_index_get_offset = dict_list_index_get_member（test_data，'offset'）
 print bisect.bisect（test_data_index_get_offset，1900）
  

它打印：

  2 
  

我的问题是这是做最好的方法吗？或者还有其他更简单，更好的方法？

解决方案

这里类似于按属性进行排序，装饰，操作和未装饰。所以在这种情况下，你只需要装饰然后调用。但是，您希望避免这样做，因为装饰将是O（n），而您希望这是O（logn）。所以我会考虑你的方法。

I have a list of dicts, something like this:

test_data = [
    { 'offset':0, 'data':1500 },
    { 'offset':1270, 'data':120 },
    { 'offset':2117, 'data':30 },
    { 'offset':4055, 'data':30000 },
]

The dict items are sorted in the list according to the 'offset' data. The real data could be much longer.

What I want to do is lookup an item in the list given a particular offset value, which is not exactly one of those values, but in that range. So, a binary search is what I want to do.

I am now aware of the Python bisect module, which is a ready-made binary search—great, but not directly usable for this case. I'm just wondering what is the easiest way to adapt bisect to my needs. Here is what I came up with:

import bisect

class dict_list_index_get_member(object):
    def __init__(self, dict_list, member):
        self.dict_list = dict_list
        self.member = member
    def __getitem__(self, index):
        return self.dict_list[index][self.member]
    def __len__(self):
        return self.dict_list.__len__()

test_data_index_get_offset = dict_list_index_get_member(test_data, 'offset')
print bisect.bisect(test_data_index_get_offset, 1900)

It prints:

2

My question is, is this the best way to do what I want, or is there some other simpler, better way?

解决方案

The usual pattern here is similar to sorting by an attribute, decorate, operate, and undecorate. So in this case you'd just need to decorate and then call. However you'd want to avoid doing this since decorate would be O(n) whereas you want this to be O(logn). Therefore I'd consider your method best.

这篇关于在Python中，使用二等分查找列表中的项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！