是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?
我在bisect模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果数字可以大于我的列表中最大的数字)。如果有更好的方法，我想知道。
为了澄清我需要这个:我知道字典将非常适合这个，但我试图保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。
使用字典是最快的方法，但(大约)会增加一倍的内存需求。
我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。
当前回答
使用dict不会使内存使用量翻倍，除非你存储的对象非常小，因为这些值只是指向实际对象的指针:
>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True
在这个例子中，'foo'只存储了一次。这对你有影响吗?我们到底要谈多少项呢?
其他回答
在维基百科http://en.wikipedia.org/wiki/Binary_search_algorithm上查看例子
def binary_search(a, key, imin=0, imax=None):
if imax is None:
# if max amount not set, get the total
imax = len(a) - 1
while imin <= imax:
# calculate the midpoint
mid = (imin + imax)//2
midval = a[mid]
# determine which subarray to search
if midval < key:
# change min index to search upper subarray
imin = mid + 1
elif midval > key:
# change max index to search lower subarray
imax = mid - 1
else:
# return index number
return mid
raise ValueError
我想使用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
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(L, x):
i = bisect.bisect_left(L, x)
if i == len(L) or L[i] != x:
return -1
return i
我需要二进制搜索python和通用的Django模型。在Django模型中，一个模型可以有外键到另一个模型，我想在检索到的模型对象上执行一些搜索。我写了下面的函数，你可以用这个。
def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
"""
This is a binary search function which search for given key in values.
This is very generic since values and key can be of different type.
If they are of different type then caller must specify `cmp` function to
perform a comparison between key and values' item.
:param values: List of items in which key has to be search
:param key: search key
:param lo: start index to begin search
:param hi: end index where search will be performed
:param length: length of values
:param cmp: a comparator function which can be used to compare key and values
:return: -1 if key is not found else index
"""
assert type(values[0]) == type(key) or cmp, "can't be compared"
assert not (hi and length), "`hi`, `length` both can't be specified at the same time"
lo = lo
if not lo:
lo = 0
if hi:
hi = hi
elif length:
hi = length - 1
else:
hi = len(values) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if not cmp:
if values[mid] == key:
return mid
if values[mid] < key:
lo = mid + 1
else:
hi = mid - 1
else:
val = cmp(values[mid], key)
# 0 -> a == b
# > 0 -> a > b
# < 0 -> a < b
if val == 0:
return mid
if val < 0:
lo = mid + 1
else:
hi = mid - 1
return -1
