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

这有点偏离主题(因为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中产生很少的额外开销.

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

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

最简单的方法是使用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

这是正确的手册:

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

我同意@ 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)