顺序查找算法和二分查找算法

查找，指在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程，本文主要介绍两种基本的查找方法：顺序查找算法和二分查找算法。

顺序查找算法

顺序查找算法又称顺序搜索算法或者线性搜索算法，是所有查找算法中最基本、最简单的，对应的时间复杂度为O(n)。顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。

Python中内置的查找函数 index() 就是顺序查找方法。

def linear_search(lst, val):
    for i,v in enumerate(lst):
        if val == v:
            return i
    return -1

lst = [1,2,3,4,5, 6, 7, 8, 9]
print(linear_search(lst, 3))

二分查找算法

二分查找又称折半查找，是在分治算法基础上设计出来的查找算法，对应的时间复杂度为O(logn)。二分查找算法仅适用于有序序列，它只能用在升序序列或者降序序列中查找目标元素。核心思想是：不断地缩小搜索区域，降低查找目标元素的难度。

def binary_search(lst, val):
    left = 0
    right = len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == val:
            return mid
        elif lst[mid] > val:  # 待查找的值在mid左侧
            right = mid - 1
        else: # 待查找的值在mid右侧
            left = mid + 1
    return -1

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(lst, 3))

算法比较

前面介绍的两个算法，时间复杂度不同，以下借助一个装饰器函数，来对比一下两个运行效率。

def calc_time(func):
    def wrapper(*args, **kwargs):
        t_b = time.time()
        result = func(*args, **kwargs)
        t_e = time.time()
        print('%s running time: %s secs.' % (func.__name__, t_e - t_b))
        return result
    return wrapper

@calc_time
def linear_search(lst, val):
    pass

@calc_time
def binary_search(lst, val):
    pass

# 修改输入数据
lst = range(100000000)
print(linear_search(lst, 31090989))
print(binary_search(lst, 31090989))

# 输出
linear_search running time: 2.874976873397827 secs.
binary_search running time: 2.002716064453125e-05 secs.

以上试验得出，当查找数据量较大时，二分查找的时间远小于顺序查找。