是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
戴夫·亚伯拉罕斯的解决方案很好。虽然我会把它做得极简:
def binary_search(L, x):
i = bisect.bisect_left(L, x)
if i == len(L) or L[i] != x:
return -1
return i
其他回答
'''
Only used if set your position as global
'''
position #set global
def bst(array,taget): # just pass the array and target
global position
low = 0
high = len(array)
while low <= high:
mid = (lo+hi)//2
if a[mid] == target:
position = mid
return -1
elif a[mid] < target:
high = mid+1
else:
low = mid-1
return -1
我想这样更好更有效。请纠正我:)。谢谢你！
S是一个列表。 Binary (s, 0, len(s) - 1, find)是初始调用。 函数返回查询项的索引。如果没有这样的项，则返回-1。 def二进制(s, p, q,找到): 如果发现= = s ((p + q) / 2): 返回(p + q) / 2 Elif p==q-1或p==q: 如果发现= = s[问]: 回来问 其他: 返回1 find < s[(p+q)/2]: 返回二进制(s p (p + q) / 2,找到) Elif find > s[(p+q)/2]: 返回二进制(s (p + q) / 2 + 1, q,找到)
这是基于一个数学断言，即(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
二分查找:
// 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))
这有点跑题了(因为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中只会引起很少的额外开销。
