是否有一个库函数可以在列表/元组上执行二分搜索，并返回找到项的位置，如果未找到则返回“False”（-1、None等）?
我在bisect module中找到了bisect_left/right函数，但是即使在列表中没有该项，它们仍然会返回一个位置。这对于它们预期的使用完全没问题，但我只想知道一个项目是否在列表中（不想插入任何东西）。
我考虑使用bisect_left，然后检查该位置上的项目是否等于我正在搜索的项目，但是这似乎很麻烦（如果数字可能大于我的清单中最大的数字，我还需要进行边界检查）。如果有更好的方法，我想知道它。
编辑为了澄清我需要这个的原因：我知道字典非常适合这个任务，但我要尽可能地减少内存消耗。我的目的是创建一种双向查找表。我在表中有一列值，我需要能够根据它们的索引访问这些值。我还希望能够找到特定值的索引或None（如果该值不在列表中）。
使用字典将是最快的方法，但将（大约）加倍内存要求。
我问这个问题是因为我认为可能已经在Python库中忽略了一些东西。正如Moe建议的那样，看来我将不得不编写自己的代码。
bisect_left函数用于在给定的有序范围内查找第一个可以插入元素并保持排序顺序的位置，如果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
pos < hi来支持a =（），x = -1，lo = 1，hi = 0的情况（空范围的结果应为-1）。同样，hi = min（hi，len（a））以支持a =（0，），x = 0，lo = 0，hi = 2（结果应为0，而不是IndexError），并且类似于lo。鉴于二分搜索在边缘处很棘手，最好是明确的，例如，对不支持的lo，hi值引发ValueError。 - jfs为什么不看一下bisect_left/right的代码，并进行适当修改以适应您的目的。
像这样：
def binary_search(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
midval = a[mid]
if midval < x:
lo = mid+1
elif midval > x:
hi = mid
else:
return mid
return -1
hi = mid 更改为 hi = mid-1，hi = len(a) 更改为 hi = len(a)-1，将 while lo < hi: 更改为 while lo <= hi，这样也是等效正确的。 - user102008def binary_search(a, x, lo = 0, hi = None):
i = bisect(a, x, lo, hi)
return i if a[i] == x else -1对于格式不当我很抱歉-不确定如何在评论区正确显示。 - Vitalibisect.bisect_left() 而不是这个。 - al45tairif midval != x and lo + 1 == hi: return -1。 - A Student at a University这有点离题（因为Moe的答案看起来已经完整回答了提问者的问题），但是考虑从头到尾查看您整个过程的复杂性可能是值得的。如果您正在使用排序列表（其中二分搜索会有所帮助）存储物品，然后仅检查存在性，则会产生以下开销（除非指定最坏情况）:
排序列表
而使用 set() 则会产生：
排序列表真正能给你的是“下一个”、“上一个”和“范围”（包括插入或删除范围），在给定起始索引的情况下为 O(1) 或 O(|range|)。如果您不经常使用这些操作，则将其存储为set，然后进行排序以供显示可能会更划算。在Python中，使用set()几乎不会带来任何额外的开销。
可能值得一提的是，现在bisect文档提供了搜索示例：http://docs.python.org/library/bisect.html#searching-sorted-lists
（抛出 ValueError 而不是返回 -1 或 None 更符合Python风格 - 例如，list.index() 就是这样做的。但当然你可以根据你的需求来调整这些示例。）
index(a, x) 解决了（二分）搜索任务。+1 - Ambareesh使用bisect最简单，检查前面一个位置以查看该项是否存在：
def binary_search(a,x,lo=0,hi=-1):
i = bisect(a,x,lo,hi)
if i == 0:
return -1
elif a[i-1] == x:
return i-1
else:
return -1
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
这个基于数学断言，即 （low + high）/ 2的底部 总是小于高限制，其中 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
high=len(t)-1 中使用变量 t？ - Rishabh Gupta我认为@DaveAbrahams的答案使用二分模块是正确的方法。但他在回答中没有提到一个重要的细节。
从文档bisect.bisect_left(a, x, lo=0, hi=len(a))
二分模块不需要预先计算搜索数组。你可以将端点直接提供给bisect.bisect_left而不是使用默认值0和len(a)。
对于我的需求更加重要，即寻找使给定函数误差最小的值X。为了做到这一点，我需要让bisect_left调用我的计算方式。这非常简单。
只需提供一个对象，该对象定义__getitem__为a
例如，我们可以使用二分算法找到任意精度的平方根！
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)
scipy.optimize 来完成此任务。 - Neil G# Generate a list
l = [n*n for n in range(1000)]
# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)
count = 0
for n in range(1000000):
# Compare with "if n in l"
if n in d:
count += 1
def binary_search(L, x):
i = bisect.bisect_left(L, x)
if i == len(L) or L[i] != x:
return -1
return i
np.searchsorted是一个有用的函数。http://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html - Roman Shapovalov