二分查找

使用递归的版本

def bin_search(lst, num, start=None, end=None):
    """
    二分查找
    :param lst: 列表
    :param num: 目标元素
    :param start: 查找的起始位置
    :param end: 查找的终止位置
    :return: 返回索引，找不到返回None
    """
    start = start if start else 0
    end = end if end else len(lst)-1
    mid = (end - start)//2 + start
    if start > end:
        return None
    elif num == lst[mid]:
        return mid
    elif num < lst[mid]:
        bin_search(lst, num, start, mid-1)
    else:
        bin_search(lst, num, mid+1, end)

分查找的效率是很高的，因为每调用一次查找范围就减半，因此只需要很少的次数就可以找到目标元素。

为了查看函数调用的次数，写了一个简单的装饰器来输出函数递归调用的次数，完整代码如下：

import time

def call_num(func):
    """
    此装饰器函数用于计算函数调用次数
    :param func:
    :return:
    """
    num = 0

    def inner(*args, **kwargs):
        nonlocal num
        ret = func(*args, **kwargs)
        num += 1
        print("function called number:", num)
        return ret
    return inner


@call_num
def bin_search(lst, num, start=None, end=None):
    """
    二分查找
    :param lst: 列表
    :param num: 目标元素
    :param start: 查找的起始位置
    :param end: 查找的终止位置
    :return: 返回索引，找不到返回None
    """
    start = start if start else 0
    end = end if end else len(lst)-1
    mid = (end - start)//2 + start
    if start > end:
        return None
    elif num == lst[mid]:
        return mid
    elif num < lst[mid]:
        bin_search(lst, num, start, mid-1)
    else:
        bin_search(lst, num, mid+1, end)

l1 = []

for i in range(100000000):
    l1.append(i)
start_time = time.time()
print(bin_search(l1, 83374292))
end_time = time.time()
print(end_time-start_time)

## 不使用递归的版本

def bin_search(lst, item):
    start = 0
    end = len(lst) - 1
    # 利用循环代替递归
    while start <= end:
        mid = (start+end)//2
        if lst[mid] == item:
            return mid
        else:
            if lst[mid] < item:
                # 从mid+1开始，否则item为列尾时程序不会终止
                start = mid+1
            else:
                end = mid-1