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

Question

是否有一个库函数在列表/元组上执行二进制搜索并返回项目的位置(如果找到)和'False'(-1,None等),如果没有？

我在bisect模块中找到了函数bisect_left/right ,但即使该项不在列表中,它们仍会返回一个位置.这对于他们的预期用途来说非常好,但我只是想知道一个项目是否在列表中(不想插入任何内容).

我想过使用bisect_left然后检查那个位置的项目是否等于我正在搜索的项目,但这看起来很麻烦(我还需要检查边界是否可以大于我列表中的最大数字).如果有一个更好的方法我想知道它.

编辑为了澄清我需要这个:我知道字典非常适​​合这个,但我试图尽可能降低内存消耗.我的预期用法是一种双向查找表.我在表中有一个值列表,我需要能够根据它们的索引访问这些值.而且如果值不在列表中,我希望能够找到特定值的索引或None.

使用字典是最快的方法,但会(大约)加倍内存需求.

我在问这个问题,认为我可能忽略了Python库中的某些东西.正如Moe建议的那样,我似乎必须编写自己的代码.

Answer 1

from bisect import bisect_left

def 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

为什么不查看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

Answer 3

这有点偏离主题(因为Moe的回答似乎完全符合OP的问题),但是从头到尾看整个过程的复杂性可能是值得的.如果您将事物存储在已排序的列表中(这是二进制搜索有帮助的地方),然后只检查是否存在,则会产生(最坏情况,除非指定):

排序列表

• O(n log n)最初创建列表(如果它是未排序的数据.O(n),如果它已排序)
• O(log n)查找(这是二进制搜索部分)
• O(n)插入/删除(可能是O(1)或O(log n)平均情况,具体取决于您的模式)

而a set(),你正在招揽

• O(n)创造
• O(1)查找
• O(1)插入/删除

在给定起始索引的情况下,排序列表真正得到的东西是"下一个","上一个"和"范围"(包括插入或删除范围),它们是O(1)或O(| range |).如果您不经常使用这些类型的操作,那么存储为集合以及排序显示可能会更好. set()在python中产生很少的额外开销.

Answer 4

值得一提的是,bisect文档现在提供了搜索示例:http: //docs.python.org/library/bisect.html#searching-sorted-lists

(例如,提高ValueError而不是返回-1或None更像pythonic - list.index()就可以了.但是当然你可以根据需要调整这些例子.)

Answer 5

最简单的方法是使用bisect并检查一个位置以查看该项目是否存在:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

Answer 6

这是正确的手册:

http://docs.python.org/2/library/bisect.html

8.5.1.搜索已排序列表

上面的bisect()函数对于查找插入点很有用,但是对于常见的搜索任务来说可能很棘手或难以使用.以下五个函数显示如何将它们转换为排序列表的标准查找:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

所以稍微修改一下你的代码应该是:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

Answer 7

我同意@ DaveAbrahams使用bisect模块的答案是正确的方法.他没有在答案中提到一个重要的细节.

来自文档 bisect.bisect_left(a, x, lo=0, hi=len(a))

二分模块不需要提前预先计算搜索数组.您只需出示端点来bisect.bisect_left代替它使用的默认值0和len(a).

对我来说更重要的是,寻找值X使得给定函数的误差最小化.为此,我需要一种让bisect_left算法调用我的计算的方法.这很简单.

只需提供一个定义__getitem__为的对象a

例如,我们可以使用bisect算法找到任意精度的平方根!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)

Answer 8

这个是：

• 不递归（这使它比大多数递归方法更节省内存）
• 实际工作
• 快速，因为它运行时没有任何不必要的if和条件
• 基于数学断言，即(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