是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
最简单的方法是使用对半分割，然后检查一个位置，看看项目是否在那里:
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
其他回答
你好，这是我的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
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
def binary_search_length_of_a_list(single_method_list):
index = 0
first = 0
last = 1
while True:
mid = ((first + last) // 2)
if not single_method_list.get(index):
break
index = mid + 1
first = index
last = index + 1
return mid
值得一提的是，bisect文档现在提供了搜索示例: http://docs.python.org/library/bisect.html#searching-sorted-lists
(引发ValueError而不是返回-1或None更加python化——例如，list.index()会这样做。当然，你也可以根据自己的需要调整这些例子。)
为什么不看看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
