顺序查找和二分查找(python)
程序员文章站
2022-03-14 20:35:44
...
顺序查找
在python List中,数据项的存储位置称为下标(有序的整数),通过下标,我们就可以按照书序来访问和查找数据项,这就是顺序查找。
- 首先从列表中的第一个数据项开始
- 按照下标增长的顺序,逐个比对数据项;
- 如果到最后一个都未发现要查找的项,那么查找失败。
类似于穷举法,穷尽所有肯能。
def list_search(alist, target):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == target:
found = True
else:
pos += 1
return pos if found else found
test_ls = [1,2,32,8,12,43,0,22,15]
target = 0
position = list_search(test_ls,target)
if position:
print('查到target,是列表的第:',position+1,'个数。')
else:
print('未查到目标数。')
输出:
查到target,是列表的第: 7 个数。
算法的复杂度是O(n)。
上述代码中的列表是无序表,接下来我们来看有序表的查找。
- 当数据项存在时,比对过程与无序表完全相同;
- 不同之处在于,如果数据项不存在,比对可以提前结束。
def order_list_search(alist, target):
pos = 0
found = False
stop = False
while pos < len(alist) and not found and not stop:
if alist[pos] == target:
found = True
else:
if alist[pos] > target:
stop = True
else:
pos += 1
return found
test_list = [0,1,3,4,5,7,8,9,10,22,33,66,100]
print(order_list_search(test_list,2))
print(order_list_search(test_list,22))
输出结果:
False
True
算法复杂度:O(n)。知识再数据项不存在时,有序表的查找能节省一些比对次数,但并不改变其数量级。
二分查找
- 有序表
- 从列表中间的项开始匹配查找
1、如果查找到,则查找结束;
2、如果中间项比target大,那么target只可能出现在前半部分;
3、如果中间项比target小,那么target只可能出现在后半部分。 - 继续采用上面的方法查找;每次都会将比对范围缩小一半。
def Binary_Search(alist, target):
left = 0
right = len(alist) - 1
found = False
while left <= right and not found:
mid = (left + right) // 2
if alist[mid] == target:
found = True
else:
if target < alist[mid]:
right = mid - 1
else:
left = mid + 1
return found
test_list = [0,1,2,8,13,17,19,22,32,42]
print(Binary_Search(test_list,8))
print(Binary_Search(test_list,23))
输出结果:
True
False
二分查找体现了解决问题的典型策略:分而治之。
- 将问题分为若干更小规模的部分;
- 通过解决每一个小规模部分问题,并将结果汇总得到原问题的解;
二分查找的递归代码
def Binary_Search(alist, target):
'''递归写法'''
if len(alist) == 0:
return False
else:
mid = len(alist) // 2
if alist[mid] == target:
return True
else:
if alist[mid] > target:
return Binary_Search(alist[:mid], target)
else:
return Binary_Search(alist[mid+1:], target)
test_list = [0,1,2,8,13,17,19,22,32,42]
print(Binary_Search(test_list,8))
print(Binary_Search(test_list,23))
二分查找复杂度:O(logn)。
注意,这里使用了列表切片,会增加开销;所以可以采用传递参数的方法。
另外,虽然二分查找在时间复杂度上优于顺序查找,但是我们也要注意对数据项进行排序也是需要开销的。
上一篇: Python实现顺序查找、二分查找
下一篇: Python 顺序查找和二分查找代码实现