- 顺序查找法
在list中,通过下标进行查找。首先从list的第1个数据项开始,按照下标增长顺序,逐个比对数据项,如果查找到最后一个都未发现要查找的项,则查找失败。
- 代码实现
#无序表查找
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).