順序查找時間復雜度為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 ireturnO(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
鏈路追蹤zipkin)
)
