算法入门——顺序查找、二分查找
顺序查找
顺序查找也叫线性查找,从列表第一个元素开始,顺序进行搜索,直到找到元素或搜索到列表最后一个元素为止。
例如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 -