一、列表查找：從列表中查找指定元素

• 輸入：列表、待查找元素
• 輸出：元素下標或未查找到元素

二、列表查找方式

• 順序查找 ： 從列表的第一個元素開始遍歷，知道找到為止。時間復雜度O(n)
• 二分查找 ：從有序的列表的候選區L[0:n]開始，通過堆待查找的值與候選區中間值進行比較，每次候選區數減少一半，時間復雜度O(logn)

順序查找

def linear_search(data_set, value):for i in range(range(data_set)):if data_set[i] == value:return ireturn

三、二分查找

不使用遞歸的方式:

def binary_search(l,n):low = 0hight = len(l)while low <= hight:mid = (low + hight) // 2if l[mid][id] < n:print(l[mid])low = mid + 1elif l[mid][id] > n:print(l[mid])hight = mid - 1else:return mid

使用遞歸的方式:

def binary_search(l,aim,start= 0,end=None):if end == None:end = len(l) - 1if start <= end:# (end - start) // 2 + start 兩種方法mid = (end + start) // 2 #12 18if l[mid] < aim:return func(l,aim,start = mid + 1,end = end) # [42,43,55,56,66,67,69,72,76,82,83,88]elif l[mid] > aim:return func(l,aim,start = start,end = mid - 1)elif l[mid] == aim:return midelse:return None

要求列表是有序的,所以python中列表的查找，并不是采用的二分查找。

四、練習

LetCode網站題目：現有一個學員信息列表（按id增序排列），格式為： stu_info = [{id:1001, "name":"張三", "age":20},{id:1002, "name":"李四", "age":25},{id:1004, "name":"王五", "age":23},{id:1007, "name":"趙六", "age":33} ] 修改二分查找代碼，輸入學生id，輸出該學生在列表中的下標，并輸出完整學生信息。 def binary_search(l,n):low = 0hight = len(l)while low <= hight:mid = (low + hight) // 2if l[mid][id] < n:print(l[mid])low = mid + 1elif l[mid][id] > n:print(l[mid])hight = mid - 1else:return midret = binary_search(stu_info,1004) print(ret)

?

轉載于:https://www.cnblogs.com/weihengblog/p/9427070.html

總結

以上是生活随笔為你收集整理的Python查找算法之 -- 列表查找和二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。