顺序查找算法是一种很基本的查找算法,该算法的复杂度一般是最大是O(n),假如加上顺序查找,算法的复杂度
还要降一倍,为O(n/2)。
Python的代码实现如下所示:
def sequential_search(a_list,item):
pos = 0
found = False while pos < len(a_list) and not found:
if a_list[pos] == item:
found = True
else:
pos = pos + 1 print("pos:%d"%pos) return found def ordered_sequential_search(a_list,item):
pos = 0
found = False
stop = False while pos < len(a_list) and not found and not stop:
if a_list[pos] == item:
found = True
else:
if a_list[pos] > item:
stop = True
else:
pos = pos + 1
print("pos:%d" % pos)
return found test_list = [1,2,8,13,17,19,32,43,0]
test_lista = [15,18,2,19,18,0,8,14,19,14]
test_listb = [3,5,6,8,11,12,14,15,17,18]
print(sequential_search(test_lista,18))
print(sequential_search(test_lista,13))
print(ordered_sequential_search(test_list,3))
print(ordered_sequential_search(test_listb,13))
运算结果:
pos:1
True
pos:10
False
pos:2
False
pos:6
False