的Python：搜索元组的排序列表

有关如何整理各种数据类型的列表，请参阅： How to sort (list/tuple) of lists/tuples?

..以及关于如何执行信息排序列表上的二进制搜索看到：Binary search (bisection) in Python

我的问题：

如何将二进制搜索（或其他日志（n）搜索算法）整齐地应用于某种数据类型的列表，其中键是数据类型本身的内部组件？为了使问题简单，我们可以使用一个元组列表为例：

x = [("a", 1), ("b",2), ("c",3)] 
binary_search(x, "b") # search for "b", should return 1 
# note how we are NOT searching for ("b",2) yet we want ("b",2) returned anyways

为了进一步简化：我们只需要返回一个搜索结果中，而不是多个例如如果（“B”，2 ）和（“b”，3）都存在。

更妙的是：

我们如何可以修改以下简单的代码来执行上述操作？

from bisect import bisect_left 

def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi 
    hi = hi if hi is not None else len(a) # hi defaults to len(a) 
    pos = bisect_left(a, x, lo, hi) # find insertion position 
    return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end

请注意：我不寻找完整的算法本身。相反，我正在寻找一些Python的标准（ish）库和/或Python的其他功能的应用程序，以便我可以随时轻松搜索任意数据类型的排序列表。

感谢

的

来源

2017-07-17 Stephen Lasky

利用顺序如何词典涉及不等长的元组：

# bisect_right would also work 
index = bisect.bisect_left(x, ('b',))

有时可方便地自定义序列类型喂bisect：

class KeyList(object): 
    # bisect doesn't accept a key function, so we build the key into our sequence. 
    def __init__(self, l, key): 
     self.l = l 
     self.key = key 
    def __len__(self): 
     return len(self.l) 
    def __getitem__(self, index): 
     return self.key(self.l[index]) 

import operator 
# bisect_right would *not* work for this one. 
index = bisect.bisect_left(KeyList(x, operator.itemgetter(0)), 'b')

来源

2017-07-18 00:02:07 user2357112

修改线5： POS = bisect_left（一，（X），LO，HI）＃查找插入位置 ...不具有所需效果，并返回一个-1未找到。 –

@StephenLasky：我只是告诉你如何找到索引。你的'binary_search'函数有其他问题;例如，它直接比较'x'到'a [pos]'，所以它不知道它找到了正确的条目。 – user2357112

我的错误，一切都很完美。出于好奇：你怎么能修改上述属性来搜索说第N个位置？ –

将元组列表转换为字典怎么样？简单二进制搜索算法来的

>>> d = dict([("a", 1), ("b",2), ("c",3)]) 
>>> d['b'] # 2

来源

2017-07-18 00:02:11 SuperShoot

这里的问题是我正在处理大量的列表（> 1,000,000），而这种操作太简单了。虽然我很欣赏你的回应。 –

的Python：搜索元组的排序列表

回答

相关问题