Article / 文章中心

Python编程:查找算法之顺序查找和二分查找

发布时间:2021-11-23 点击数:208

算法Algorithm

一个计算过程,解决问题的方法


递归:


调用自身

结束条件

时间复杂度:


用来估计算法运行时间的一个式子

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n2logn) < O(n^3)

一般来说,时间复杂度高的算法比复杂度低的算法慢


不常见的时间复杂度:

O(n!) O(2^n) O(n^n)


时间复杂度判断


循环减半的过程 -> O(logn)

几次循环就是n的几次方

空间复杂度:


用来评估算法内存占用大小的式子

空间换时间


列表查找

从列表中查找指定元素

输入:列表,待查元素

输出:元素下标或未查找到元素

顺序查找:


从列表第一个元素开始,顺序进行搜索,直到找到为止

二分查找:


从有序列表的候选区data[0: n]开始,通过对待查找的值与候选区中间的值比较,可以使候选区减少一半

代码实例

1、递归

#先打印再调用 def foo1(x):  if x > 0:  print(x)  foo1(x-1)  foo1(5) # 5 4 3 2 1  # 先调用再打印 def foo2(x):  if x > 0:  foo2(x-1)  print(x)  foo2(5) # 1 2 3 4 5

2、顺序查找与二分查找

# -*- coding: utf-8 -*-  import time  # 计时装饰器 def timer(func):  def wrapper(*args, **kwargs):  start = time.time()  ret = func(*args, **kwargs)  end = time.time()  print("time: %s"% (end-start))  return ret  return wrapper   # 顺序(线性)查找 O(n) @timer def line_search(lst, val):  for index, value in enumerate(lst):  if val == value:  return index   return None  # 二分查找(需要有序) O(logn) @timer def binary_search(lst, val):  low = 0  high = len(lst) - 1   while low <= high:  mid = (high + low)//2  if lst[mid] == val:  return mid  elif lst[mid] < val:  low = mid + 1  else:  high = mid - 1   return None   if __name__ == '__main__':  lst = list(range(100000))   ret = line_search(lst, 90000)  print(ret)  # time: 0.007  # 90000   ret = binary_search(lst, 90000)  print(ret)  # time: 0.000  # 90000

3、二分查找实例

  • 通过二分查找,输入id 查找学生完整信息
# -*- coding: utf-8 -*-  import random from chinesename import chinesename  # pip install chinesename  # 二分查找函数 def binary_search(lst, uid):  low = 0  high = len(lst) - 1   while low <= high:  mid = (low + high)//2  if lst[mid]["uid"] == uid:  return lst[mid]  elif lst[mid]["uid"] < uid:  low = mid + 1  else:  high = mid - 1   return None  # 生成学生信息 def get_students(n):  """  @param n: 数量  @return: {list}  """   cn = chinesename.ChineseName()   uids = list(range(1001, 1001+n))  lst = []  for uid in uids:  dct = {  "uid": uid,  "name": cn.getName(),  "age": random.randint(18, 60)  }  lst.append(dct)   return lst   if __name__ == '__main__':  students = get_students(100000)   ret = binary_search(students, 1005)   print(ret)  # {'uid': 1005, 'name': '相佃', 'age': 58}