二分查找

àì夳堔傛蜴生んèń 2022-01-07 04:03 79阅读 0赞

## 使用递归的版本 ##

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

转载于:https://www.cnblogs.com/zzliu/p/10679844.html