Python編程：查找算法之順序查找和二分查找
發(fā)布時(shí)間：2021-11-23 點(diǎn)擊數(shù)：622
算法Algorithm
一個(gè)計(jì)算過程，解決問題的方法
遞歸：
調(diào)用自身
結(jié)束條件
時(shí)間復(fù)雜度：
用來估計(jì)算法運(yùn)行時(shí)間的一個(gè)式子
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n2logn) < O(n^3)
一般來說，時(shí)間復(fù)雜度高的算法比復(fù)雜度低的算法慢
不常見的時(shí)間復(fù)雜度：
O(n!) O(2^n) O(n^n)
時(shí)間復(fù)雜度判斷
循環(huán)減半的過程 -> O(logn)
幾次循環(huán)就是n的幾次方
空間復(fù)雜度：
用來評估算法內(nèi)存占用大小的式子
空間換時(shí)間
列表查找
從列表中查找指定元素
輸入：列表，待查元素
輸出：元素下標(biāo)或未查找到元素
順序查找：
從列表第一個(gè)元素開始，順序進(jìn)行搜索，直到找到為止
二分查找：
從有序列表的候選區(qū)data[0: n]開始，通過對待查找的值與候選區(qū)中間的值比較，可以使候選區(qū)減少一半
代碼實(shí)例
1、遞歸
#先打印再調(diào)用 def foo1(x): if x > 0: print(x) foo1(x-1) foo1(5) # 5 4 3 2 1 # 先調(diào)用再打印 def foo2(x): if x > 0: foo2(x-1) print(x) foo2(5) # 1 2 3 4 5
2、順序查找與二分查找
# -*- coding: utf-8 -*- import time # 計(jì)時(shí)裝飾器 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、二分查找實(shí)例
- 通過二分查找，輸入id 查找學(xué)生完整信息
# -*- coding: utf-8 -*- import random from chinesename import chinesename # pip install chinesename # 二分查找函數(shù) 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 # 生成學(xué)生信息 def get_students(n): """ @param n: 數(shù)量 @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}