Python编程：查找算法之顺序查找和二分查找

算法Algorithm

一个计算过程，解决问题的方法

递归：

• 调用自身
• 结束条件

时间复杂度：

• 用来估计算法运行时间的一个式子 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n2logn) < O(n^3)

• 一般来说，时间复杂度高的算法比复杂度低的算法慢

• 不常见的时间复杂度： O(n!) O(2^n) O(n^n)

时间复杂度判断

• 循环减半的过程 -> O(logn)
• 几次循环就是n的几次方

空间复杂度：

• 用来评估算法内存占用大小的式子

空间换时间

列表查找

• 从列表中查找指定元素
• 输入：列表，待查元素
• 输出：元素下标或未查找到元素

顺序查找：

• 从列表第一个元素开始，顺序进行搜索，直到找到为止

二分查找：

• 从有序列表的候选区data[0: n]开始，通过对待查找的值与候选区中间的值比较，可以使候选区减少一半

代码实例

1、递归

#先打印再调用
def foo1(x):
    if x > 0:
        print(x)
        foo1(x-1)

foo1(5)
# 5 4 3 2 1

# 先调用再打印
def foo2(x):
    if x > 0:
        foo2(x-1)
        print(x)

foo2(5)
# 1 2 3 4 5

2、顺序查找与二分查找

# -*- coding: utf-8 -*-

import time

# 计时装饰器
def timer(func):
    def wrapper(*args, **kwargs):
        start = time.time()
        ret = func(*args, **kwargs)
        end = time.time()
        print("time: %s"% (end-start))
        return ret
    return wrapper


# 顺序（线性）查找 O(n)
@timer
def line_search(lst, val):
    for index, value in enumerate(lst):
        if val == value:
            return index

    return None

# 二分查找(需要有序) O(logn)
@timer
def binary_search(lst, val):
    low = 0
    high = len(lst) - 1

    while low