顺序查找

从列表中的第一个项目开始，我们按照基本的顺序排序，简单地从一个项移动到另一个项，直到找到我们正在寻找的项或遍历完整个列表。如果我们遍历完整个列表，则说明正在搜索的项不存在。

def sequentialSearch(alist, item):
    pos = 0
    found = False
    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos+1
    return found
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

顺序查找分析

二分查找

这个算法是分而治之策略的一个很好的例子。分和治意味着我们将问题分成更小的部分，以某种方式解决更小的部分，然后重新组合整个问题以获得结果。 当我们执行列表的二分查找时，我们首先检查中间项。如果我们正在搜索的项小于中间项，我们可以简单地对原始列表的左半部分执行二分查找。同样，如果项大，我们可以执行右半部分的二分查找。 无论哪种方式，都是递归调用二分查找函数

def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
    if alist[midpoint]==item:
        return True
    else:
        if item<alist[midpoint]:
            return binarySearch(alist[:midpoint],item)
        else:
            return binarySearch(alist[midpoint+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

时间复杂度

import random
if __name__=='__main__':
    def sequentialSearch(alist, item):
        pos = 0
        found = False
        while pos < len(alist) and not found:
            if alist[pos] == item:
                found = True
            else:
                pos = pos+1
        return found

    def binarySearch(alist, item):
        if len(alist) == 0:
            return False
        else:
            midpoint = len(alist)//2
        if alist[midpoint]==item:
            return True
        else:
            if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],item)
            else:
                return binarySearch(alist[midpoint+1:],item)

    sequentialSearch_nlogn = []
    binarySearch_nlogn = []

    sequential_c = Timer("sequentialSearch(new_list, new_item)", "from __main__ import sequentialSearch,new_list,new_item")
    binary_c = Timer("binarySearch(new_list, new_item)", "from __main__ import binarySearch,new_list,new_item")

    x = list(range(100,4000,100))

    for i in x:
        new_list = list(range(i))
        new_item = random.choice(new_list)
        sequentialSearch_nlogn.append(sequential_c.timeit(number = 100))
        binarySearch_nlogn.append(binary_c.timeit(number = 100))

    plt.plot(x, sequentialSearch_nlogn,marker='o',label='sequentialSearch')
    plt.plot(x, binarySearch_nlogn,marker='o',label='binarySearch')

    plt.legend()  # 让图例生效
    plt.xlabel('n size')  # X轴标签
    plt.ylabel("time use")  # Y轴标签

    plt.show()