是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
虽然Python中没有显式的二进制搜索算法，但有一个模块- bisect -用于使用二进制搜索在排序列表中找到元素的插入点。这可以被“欺骗”为执行二分搜索。它最大的优势和大多数库代码一样——它是高性能的，经过良好测试的，并且可以正常工作(特别是二进制搜索很难成功实现——特别是在没有仔细考虑边缘情况的情况下)。
基本类型
对于基本类型，如string或int，这是非常简单的-你只需要bisect模块和一个排序列表:
>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False
你也可以用它来查找副本:
...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']
显然，如果需要，您可以只返回索引，而不是该索引处的值。
对象
对于自定义类型或对象，事情有点棘手:您必须确保实现丰富的比较方法，以便正确地进行比较。
>>> import bisect
>>> class Tag(object): # a simple wrapper around strings
... def __init__(self, tag):
... self.tag = tag
... def __lt__(self, other):
... return self.tag < other.tag
... def __gt__(self, other):
... return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']
这应该至少在Python 2.7 -> 3.3中工作
其他回答
我需要二进制搜索python和通用的Django模型。在Django模型中，一个模型可以有外键到另一个模型，我想在检索到的模型对象上执行一些搜索。我写了下面的函数，你可以用这个。
def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
"""
This is a binary search function which search for given key in values.
This is very generic since values and key can be of different type.
If they are of different type then caller must specify `cmp` function to
perform a comparison between key and values' item.
:param values: List of items in which key has to be search
:param key: search key
:param lo: start index to begin search
:param hi: end index where search will be performed
:param length: length of values
:param cmp: a comparator function which can be used to compare key and values
:return: -1 if key is not found else index
"""
assert type(values[0]) == type(key) or cmp, "can't be compared"
assert not (hi and length), "`hi`, `length` both can't be specified at the same time"
lo = lo
if not lo:
lo = 0
if hi:
hi = hi
elif length:
hi = length - 1
else:
hi = len(values) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if not cmp:
if values[mid] == key:
return mid
if values[mid] < key:
lo = mid + 1
else:
hi = mid - 1
else:
val = cmp(values[mid], key)
# 0 -> a == b
# > 0 -> a > b
# < 0 -> a < b
if val == 0:
return mid
if val < 0:
lo = mid + 1
else:
hi = mid - 1
return -1
虽然Python中没有显式的二进制搜索算法，但有一个模块- bisect -用于使用二进制搜索在排序列表中找到元素的插入点。这可以被“欺骗”为执行二分搜索。它最大的优势和大多数库代码一样——它是高性能的，经过良好测试的，并且可以正常工作(特别是二进制搜索很难成功实现——特别是在没有仔细考虑边缘情况的情况下)。
基本类型
对于基本类型，如string或int，这是非常简单的-你只需要bisect模块和一个排序列表:
>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False
你也可以用它来查找副本:
...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']
显然，如果需要，您可以只返回索引，而不是该索引处的值。
对象
对于自定义类型或对象，事情有点棘手:您必须确保实现丰富的比较方法，以便正确地进行比较。
>>> import bisect
>>> class Tag(object): # a simple wrapper around strings
... def __init__(self, tag):
... self.tag = tag
... def __lt__(self, other):
... return self.tag < other.tag
... def __gt__(self, other):
... return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']
这应该至少在Python 2.7 -> 3.3中工作
这是基于一个数学断言，即(low + high)/2的下限总是小于high，其中low是下限，high是上限。
def binsearch(t, key, low = 0, high = len(t) - 1):
# bisecting the range
while low < high:
mid = (low + high)//2
if t[mid] < key:
low = mid + 1
else:
high = mid
# at this point 'low' should point at the place
# where the value of 'key' is possibly stored.
return low if t[low] == key else -1
这有点跑题了(因为Moe的回答似乎完整地回答了OP的问题)，但从头到尾考虑整个过程的复杂性可能是值得的。如果你把东西存储在一个排序的列表中(这是二进制搜索会有帮助的地方)，然后只是检查是否存在，你会遇到(最坏情况，除非指定):
排序的列表
O(n log n)来初始创建列表(如果它是未排序的数据。O(n)，如果是排序的) O(log n)次查找(这是二分查找部分) O(n)插入/删除(可能是O(1)或O(log n)平均情况，这取决于您的模式)
而使用set()则会导致
O(n)来创造 O(1)查找 O(1)插入/删除
一个排序列表真正让你得到的是“下一个”，“前一个”和“范围”(包括插入或删除范围)，它们是O(1)或O(|范围|)，给定一个起始索引。如果你不经常使用这些类型的操作，那么存储为集合，排序显示可能是一个更好的整体交易。Set()在python中只会引起很少的额外开销。
S是一个列表。 Binary (s, 0, len(s) - 1, find)是初始调用。 函数返回查询项的索引。如果没有这样的项，则返回-1。 def二进制(s, p, q,找到): 如果发现= = s ((p + q) / 2): 返回(p + q) / 2 Elif p==q-1或p==q: 如果发现= = s[问]: 回来问 其他: 返回1 find < s[(p+q)/2]: 返回二进制(s p (p + q) / 2,找到) Elif find > s[(p+q)/2]: 返回二进制(s (p + q) / 2 + 1, q,找到)
