Python中的二进制搜索(二等分)
是否有一个库函数可以对列表/元组执行二进制搜索，如果找到，则返回项目的位置和'False‘(-1，None等)如果不是呢？
我在bisect module中找到了函数bisect_left/right，但即使项目不在列表中，它们也会返回一个位置。这对于他们的预期用途来说是非常好的，但我只想知道一个项目是否在列表中(不想插入任何东西)。
我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的项，但这似乎很麻烦(而且我还需要做边界检查，看看这个数字是否可以大于我列表中的最大数)。如果有更好的方法，我很想知道。
编辑来阐明我需要它做什么:我知道字典非常适合这一点，但我正在努力保持尽可能低的内存消耗。我的预期用途是一种双向查找表。我在表中有一个值列表，并且我需要能够基于它们的索引访问值。我还希望能够找到特定值的索引，或者如果该值不在列表中，则不查找索引。
使用字典来实现这一点是最快的方法，但会(大约)将内存需求增加一倍。
我问这个问题的时候，我想我可能忽略了Python库中的一些东西。看起来我不得不像Moe建议的那样写我自己的代码。
回答 20
Stack Overflow用户
发布于 2010-02-10 10:05:28
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 endStack Overflow用户
发布于 2008-10-17 14:36:49
为什么不看看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 -1Stack Overflow用户
发布于 2008-10-17 16:59:57
这有点离题(因为Moe的答案似乎完全回答了OP的问题)，但从头到尾看一下整个过程的复杂性可能是值得的。如果你把东西存储在一个排序的列表中(这是二进制搜索会有帮助的地方)，然后只是检查是否存在，你就会招致(最坏的情况，除非指定)：
排序列表
- O( N log n)用于初始创建列表(如果它是未排序的数据。O( n)，如果已排序)
- O( log )查找(这是二进制搜索部分)
- O( n)插入/删除(可能是O(1)或O( log )平均大小写，取决于您的模式)
而使用set()，你会招致
- O(n) to create
- O(1) lookup
- O(1) insert / delete
排序列表真正得到的是“下一个”、“上一个”和“范围”(包括插入或删除范围)，它们是O(1)或O(|range|)，给定一个起始索引。如果您不经常使用这些类型的操作，那么将其存储为集合，并进行排序以进行显示，总体上可能会更好。在python中，set()带来的额外开销很小。
https://stackoverflow.com/questions/212358
复制相似问题