排序算法的python实现及算法分析——二分查找(Binary Search)

二分查找：
在有序表的前提下采用分而治之（从中间项开始），这样对比范围就可以缩小为n/2,
查找过程与实现原理：
将问题分解为若干更小规模部分的问题，并将结果汇总得到原问题的解

python实现代码：

###二分查找  普通版

def binarysearch(alist,item):
    first=0
    last=len(alist)-1
    found=False

    while first<=last and not found:
        midpoint=(first+last)//2
        if alist[midpoint]==item:
            found=True
        else:
            if item < alist[midpoint]:
                last=midpoint-1
            else:
                first =midpoint+1
    return found
## 测试实例
testlist1=[0,1,3,8,10,17,19,32,43]
print(binarysearch(testlist1,3))   	#True
print(binarysearch(testlist1,13))   #False

二分查找，在有序的前提下，先划分区间，然后对比中间项，缩小问题规模，在划分区间，接着对比然后缩小规模，恰好是递归算法的求解思路.。

## 二分查找，递归版

def binarysearch2(alist,item):
    if len(alist)==0:
        return False     ##基本结束条件
    else:
        midpoint=len(alist)//2
        if alist[midpoint]==item:
            return True
        else:
            if item <alist[midpoint]:
                return binarysearch2(alist[: midpoint],item)   #调用自身
            else:
                return binarysearch2(alist[midpoint+1 :],item)
##测试实例
testlist1=[0,1,3,8,10,17,19,32,43]
print(binarysearch2(testlist1,13))     # False
print(binarysearch2(testlist1,3))      # True

算法分析：
二分查找每次比对都将范围缩小一半，因此第i次时，其剩下范围为n/2^i，
对比次数足够多时，范围内就会仅剩1个数据项。因此得到： i=log2(n)
综上：二分查找的算法复杂度为O(log n)

注意：二分查找时需要考虑对数据项进行排序的开销，若仅排序一次，可忽略其时间，若数据经常变动，则排序耗时长，可能还没顺序查找来的快！