Python：数据结构及算法（1）——查找

查找

顺序查找

时间复杂度O(n)

# 顺序查找 # 返回值为列表索引 def liner_search(li, val): for index, v in enumerate(li): if v == val: return index else: return None

二分查找

时间复杂度O(logn)

# 二分查找 # lis位从小到大的有序列表 # 返回值为列表索引 def binary_search(lis, val): left = 0 right = len(lis)-1 while left <= right: # 候选区有值 mid = (left + right) // 2 if val == lis[mid]: return mid elif val < lis[mid]: # 值在左侧候选区 right = mid-1 else: left = mid + 1 else: return None

运行

if __name__ == '__main__': li = [1, 2, 3, 5, 6, 8] # 顺序查找 ind = liner_search(li=li, val=2) # 要在列表中查找的值为 2 print(li[ind]) print('顺序查找值位2的列表索引为：', ind) # 二分查找 mid = liner_search(li=li, val=6) # 要在列表中查找的值为 6 print(li[mid]) print('顺序查找值位6的列表索引为：', mid)

运行结果

2 顺序查找值位2的列表索引为： 1 6 顺序查找值位6的列表索引为： 4