数据结构与算法(13)—顺序查找法

  • 顺序查找法

在list中,通过下标进行查找。首先从list的第1个数据项开始,按照下标增长顺序,逐个比对数据项,如果查找到最后一个都未发现要查找的项,则查找失败。

数据结构与算法(13)—顺序查找法

  • 代码实现
#无序表查找
def sequentialSearch(alist, item): pos = 0 found = False while pos < len(alist) and not found: if alist[pos] == item: found = True else: pos += 1 return found testliat = [1, 2, 32, 8, 17, 19, 42, 13, 0] print(sequentialSearch(testliat, 3)) print(sequentialSearch(testliat, 13))
#顺序表
def orderSequentialSearch(alist, item):
    '''
    :param alist: 有序表
    :param item: 查找对象
    :return: 查找结果bool类型
    '''
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos = pos + 1
    return found
testliat = [0, 1, 2,8, 13, 17, 19, 32, 42, ]
print(orderSequentialSearch(testliat, 3))
print(orderSequentialSearch(testliat, 13))

 

  • 分析

1.比对次数:如果数据项不在list中,比对次数为n,当在list中,比对次数为1~n。因此顺序查找的复杂度是o(n).

 

上一篇:算法-04-选择排序


下一篇:在java中,怎么样使ArrayList重新排序,倒转排序?