赞
踩
目录
顺序查找也叫线性查找,从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后一个元素为止。
例如1~100的数字,如果我们想要的数字为100,那么程序需要查找100次才能找到。所以顺序查找称为傻找。
顺序查找代码逻辑:通过for循环遍历列表的值和下标,再将值与你想查找的值作比较,两值相等就返回该值的下标即可。
示例代码如下:
- li=[1,2,5,3,'十',6,8,9]
- def linear_search(li,value):
- for i,v in enumerate(li): # 遍历li列表的值和下标
- if v==value:
- return i
- print(linear_search(li,8))
这里使用enumerate方法获取列表元素的值和下标。
顺序查找的时间复杂度为:O(n)。
二分查找是从有序列表的中间位置开始查找,每次查找后进行判断满足要求的元素在左边还是在右边。
例如:我们从1~15的数字中查找6这个数字,使用二分查找查找如下图所示:
如上图所示:使用二分查找时,每次都能排除一半的数字,这样我们只需要查找3次就可以找到满足查找要求的元素。
二分查找的实现关键在于:区分好满足条件的元素左右区域。
示例代码如下:
- def binary_search(li, val):
- left = 0
- right = len(li) - 1
- while left <= right: # 候选区有值
- mid = (left + right) // 2
- if li[mid] == val:
- return f'查找元素的下标为:{mid}'
- elif li[mid] > val: # 待查找的值在中间位置的左侧
- right = mid - 1
- print('满足条件的列表元素有:',li[left:right+1])
- else: # 待查找的值在中间位置的右侧
- left=mid +1
- print('满足条件的列表元素有:',li[left:right+1])
- else:
- return '你查找的元素不在列表中'
- print(binary_search([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],6))
运行结果如下:
这样就成功获取到了6这个元素的下标5了。
二分查找的时间复杂度为:O(logn)。
好了,关于算法入门——顺序查找、二分查找就学到这里,下篇文章我们学习算法入门——冒泡排序、选择排序。
- END -
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。