算法007_二分查找与线性查找的比较

时间复杂度
线性查找的时间复杂度是 ，二分查找因为有折半的过程，时间复杂度为

时间的比较
使用装饰器来计算算法运行的时间

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print(f"函数 {func.__name__} 运行的时间是 {end_time - start_time} 秒")
        return result
    return wrapper

完整代码

import time


def cal_time(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print(f"函数 {func.__name__} 运行的时间是 {end_time - start_time} 秒")
        return result
    return wrapper


@cal_time
def linear_search(target_list, target_value):
    for index, val in enumerate(target_list):
        if val == target_value:
            return index
    else:
        return None


@cal_time
def binary_search(target_list, target_value):
    left = 0
    right = len(target_list) - 1
    while left <= right:  
        mid = (left + right) // 2  
        if target_list[mid] == target_value:
            return mid
        elif target_list[mid] > target_value:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return None


test_list = list(range(100000000))
linear_search(test_list, 1234567)
binary_search(test_list, 1234567)

运行结果

函数 linear_search 运行的时间是 0.08768105506896973 秒
函数 binary_search 运行的时间是 5.888938903808594e-05 秒

0.08 / ( 5.88 * 10^-5）= 1360，二分查找的效率约是线性查找的一千倍

注意
Python 的内置函数 Index() 使用的是线性查找，因为二分查找要求列表必须是有序的
如果是有序列表，可以使用线性查找。如果是无序的，就使用线性查找
如果要查找的次数非常多，可以先排序，再使用二分查找