顺序查找时间复杂度为O(n)

我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值

def linnear_search(li, val):for ind, v in enumerate(li):if v == val:return indelse:return None

也可以通过列表长度依次遍历:

def linear_search(li, val):     # 顺序查找复杂度为O(n)for i in range(len(li)):if li[i]==val:return ireturn

O(1)<O(logn)<O(n)<O(nlogn)<O(n*n)

但是二分查找时间复杂度为O(logn):

def binary_search(li,val):left=0right=len(li)-1while left<=right:mid=(left+right) // 2if li[mid]==val:    # 最后会找到midreturn midelif li[mid]>val:   # mid值大与查找值,就需要去左半侧查找,right指针就改变right=mid-1else:left=mid+1else:return None