顺序查找时间复杂度为O(n)
我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值
def linnear_search(li, val):
for ind, v in enumerate(li):
if v == val:
return ind
else:
return None
也可以通过列表长度依次遍历:文章来源:https://www.toymoban.com/news/detail-650794.html
def linear_search(li, val): # 顺序查找复杂度为O(n)
for i in range(len(li)):
if li[i]==val:
return i
return
O(1)<O(logn)<O(n)<O(nlogn)<O(n*n)
但是二分查找时间复杂度为O(logn):文章来源地址https://www.toymoban.com/news/detail-650794.html
def binary_search(li,val):
left=0
right=len(li)-1
while left<=right:
mid=(left+right) // 2
if li[mid]==val: # 最后会找到mid
return mid
elif li[mid]>val: # mid值大与查找值,就需要去左半侧查找,right指针就改变
right=mid-1
else:
left=mid+1
else:
return None
到了这里,关于数据结构算法--1 顺序查找二分查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!