是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
这段代码以递归的方式处理整数列表。寻找最简单的情况，即:列表长度小于2。这意味着答案已经存在，并执行测试以检查正确答案。 如果不正确，则设置中间值并测试其是否正确，如果不正确，则再次调用该函数，但将中间值设置为上限或下限，将其向左或向右移动
def binary_search(intList, intValue, lowValue, highValue):
if(highValue - lowValue) < 2:
return intList[lowValue] == intValue or intList[highValue] == intValue
middleValue = lowValue + ((highValue - lowValue)/2)
if intList[middleValue] == intValue:
return True
if intList[middleValue] > intValue:
return binary_search(intList, intValue, lowValue, middleValue - 1)
return binary_search(intList, intValue, middleValue + 1, highValue)
其他回答
二分查找:
// List - values inside list
// searchItem - Item to search
// size - Size of list
// upperBound - higher index of list
// lowerBound - lower index of list
def binarySearch(list, searchItem, size, upperBound, lowerBound):
print(list)
print(upperBound)
print(lowerBound)
mid = ((upperBound + lowerBound)) // 2
print(mid)
if int(list[int(mid)]) == value:
return "value exist"
elif int(list[int(mid)]) < value:
return searchItem(list, value, size, upperBound, mid + 1)
elif int(list[int(mid)]) > value:
return searchItem(list, value, size, mid - 1, lowerBound)
//调用上述函数使用:
list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))
这是基于一个数学断言，即(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
如果你只是想看看它是否存在，试着把这个列表变成一个词典:
# 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
在我的机器上，“if n in l”需要37秒，而“if n in d”需要0.4秒。
为什么不看看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
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
