是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
我同意@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)
其他回答
我想使用bisect_left，然后检查是否在那项 position等于我要搜索的内容，但这看起来很麻烦 (我还需要做边界检查，如果数字可以更大 而不是我列表中最大的数字)。如果有更好的方法，我会 我想了解一下。
避免边界检查或相等性检查的一种方法是同时运行bisect_left()和bisect_right():
def find(data, target):
start = bisect_left(data, target)
end = bisect_right(data, target)
return -1 if start == end else start
使用dict不会使内存使用量翻倍，除非你存储的对象非常小，因为这些值只是指向实际对象的指针:
>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True
在这个例子中，'foo'只存储了一次。这对你有影响吗?我们到底要谈多少项呢?
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)
戴夫·亚伯拉罕斯的解决方案很好。虽然我会把它做得极简:
def binary_search(L, x):
i = bisect.bisect_left(L, x)
if i == len(L) or L[i] != x:
return -1
return i
