Python中的二进制搜索(二分法)

Question

Python中的二进制搜索(二分法)

是否有一个库函数可以对列表/元组执行二进制搜索，如果找到并返回项的位置和‘false’(-1，无，等等)如果不是？

我在平分模，但即使项目不在列表中，它们仍然返回一个位置。对于它们的预期用途来说，这是非常好的，但我只想知道列表中是否有项目(不想插入任何内容)。

我想用bisect_left然后检查位于该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(我还需要进行边界检查，以检查该数字是否可以大于我列表中最大的数字)。如果有更好的方法，我想知道。

编辑为了澄清我需要它做什么：我知道字典将非常适合这一点，但我正试图尽可能地降低内存消耗。我打算用的是一张双向查表。表中有一个值列表，我需要能够根据它们的索引访问这些值。另外，我希望能够找到某个特定值的索引，如果该值不在列表中，则为零。

为此使用字典将是最快的方法，但将(大约)增加一倍的内存需求。

我在问这个问题时认为，我可能忽略了Python库中的一些内容。看来我得自己写代码了，就像Moe建议的那样。

3 回答

Answer 1

from bisect import bisect_leftdef binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi     hi = hi if hi is not None else len(a)  # hi defaults to 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

Answer 2

为什么不看一下二分法的代码左/右，并调整它，以适应您的目的。就像这样：def&nbsp;binary_search(a,&nbsp;x,&nbsp;lo=0,&nbsp;hi=None): &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;hi&nbsp;is&nbsp;None: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hi&nbsp;=&nbsp;len(a) &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;lo&nbsp;<&nbsp;hi: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;mid&nbsp;=&nbsp;(lo+hi)//2 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;midval&nbsp;=&nbsp;a[mid] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;midval&nbsp;<&nbsp;x: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lo&nbsp;=&nbsp;mid+1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elif&nbsp;midval&nbsp;>&nbsp;x:&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;hi&nbsp;=&nbsp;mid&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;mid&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;-1