文章概述

1. 二分查找法介绍
2. 简单查找与二分查找对比

二分查找

 二分查找算法主要思想：在有序列表中查找指定元素，先从列表的中间查找，比较中间元素与目标元素的大小，然后在剩余的一半列表中继续这样查找，每次查找都能过滤掉一半元素。最多需要查找logn次，那么时间复杂度是O(logn)。记住：列表必须有序。
 例子：在列表1-100直接查找目标元素60

1. 找到中间元素50，与60比较，目标元素大于中间元素，那么在50-100间查找
2. 50到100中间元素75，依次循环，直到找到60为止。
   python实现：

def binary_search(l, value):
    '''
    l是有序列表，value是目标元素
    '''
    start = 0
    end = len(l) - 1

    t = 0  # 查找次数

    while end >= start:
        t += 1
        mid = int((start+end)/2)
        guess = l[mid]
        if guess < value:
            start = mid + 1
        elif guess > value:
            end = mid - 1
        else:
            print("查找次数%d" % t)
            return mid

    return False

二分查找效率

 二分查找算法的效率如何，我们做个试验与简单查找来对比
 我们首先写个时间装饰器来记录算法运行的时间

def timeit(func):
    """打印时间"""
    def new_func(self, *args, **kwargs):
        now = time.time()
        ret = func(self, *args, **kwargs)
        ms = 1000 * (time.time() - now)
        print("%s() in %.3fms.", func.__name__, ms)
        return ret
    return new_func

简单查找算法
@timeit
def single(l,value):
    t = 0  # 查找次数
    for i,v in enumerate(l[::-1]):
        t += 1
        if v == value:
            print("查找次数%d" % t)
            return i
    return False

• 列表长度为1000
  简单查找：最大次数1000，最差时间0.063ms.
  二分查找：最大次数10，最差时间0.034ms.
• 列表长度为100000
  简单查找：最大次数100000，最差时间6.096ms.
  二分查找：最大次数17，最差时间0.028ms.
• 列表长度为1000000
  简单查找：最大次数1000000，最差时间66.096ms.
  二分查找：最大次数17，最差时间0.042ms.

可见，简单查找次数和时间呈线性增长，列表长度越大，消耗时间和次数越多，但适用条件广泛，类似list的index方法。而二分查找呈对数增长，列表长度越大，消耗时间和次数增加不明显，但是二分查找适用条件不广泛，必须是有序的列表

image.png