是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
这有点跑题了(因为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中只会引起很少的额外开销。
其他回答
Bisect_left找到在给定的排序范围内插入元素的第一个位置p，同时保持排序顺序。如果x在值域内，这就是x的位置。如果p是超过末端的位置，x就找不到。否则，我们可以测试x是否在那里，看看是否找到了x。
from bisect import bisect_left
def binary_search(a, x, lo=0, hi=None):
if hi is None: hi = 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
我同意@DaveAbrahams使用等分模块的答案是正确的方法。他在回答中没有提到一个重要的细节。
从文档中平分。Bisect_left (a, x, lo=0, hi=len(a))
平分模块不需要预先计算搜索数组。你可以把端点表示为等分线。Bisect_left，而不是使用默认值0和len(a)。
对我的使用更重要的是，寻找一个值X，使给定函数的误差最小化。要做到这一点，我需要一种方法让bisect_left的算法调用我的计算。这真的很简单。
只需要提供一个对象，将__getitem__定义为
例如，我们可以使用平分算法以任意精度找到一个平方根!
import bisect
class sqrt_array(object):
def __init__(self, digits):
self.precision = float(10**(digits))
def __getitem__(self, key):
return (key/self.precision)**2.0
sa = sqrt_array(4)
# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)
虽然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实现没有平分。如果可以改进，请告诉我。
def bisectLeft(a, t):
lo = 0
hi = len(a) - 1
ans = None
# print("------lower------")
# print(a, t)
while lo <= hi:
mid = (lo + hi) // 2
# print(a[lo:mid], [a[mid]], a[mid:hi])
if a[mid] < t:
lo = mid + 1
elif a[mid] > t:
hi = mid - 1
elif a[mid] == t:
if mid == 0: return 0
if a[mid-1] != t: return mid
hi = mid - 1
return ans
def bisectRight(a, t):
lo = 0
hi = len(a) - 1
ans = None
# print("------upper------")
# print(a, t)
while lo <= hi:
mid = (lo + hi) // 2
# print(a[lo:mid], [a[mid]], a[mid:hi])
if a[mid] == t:
ans = mid
if a[mid] <= t:
lo = mid + 1
else:
hi = mid - 1
return ans
这是手册上的内容:
http://docs.python.org/2/library/bisect.html
8.5.1. 搜索排序列表
上面的bisect()函数在查找插入点时很有用，但在执行普通搜索任务时可能会有些棘手或尴尬。下面5个函数展示了如何将它们转换为排序列表的标准查找:
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
因此，稍微修改一下你的代码应该是:
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
return -1
