演算法 | 二進位搜尋演算法---使用Python3

演算法 | 二進位搜尋演算法---使用Python3

估計會寫一系列以Python 3 為實作的演算法紀錄文章，一方面是作為筆記記錄自己當除如何理解演算法，另一方面是透過輸出(分享)，可以增進自己的理解。

二進位搜尋演算法

時間複雜度O(log n)，註：此處的log以2為底。

二進位搜尋演算法常跟簡易搜尋演算法做比較，透過時間複雜度O的不同，理解處理速度的不同，如下表所示：

時間複雜度O	演算法
O(log n)	二進位搜尋法
O(n)	簡易搜尋法

n為項目數。


例如要搜尋一串數列，數值介於1~100，那項目數n有100個，使用二進位搜尋演算法最壞的情況下所需時間為log100(log以2為底)次，簡易搜尋法最壞的情況下所需時間為100次。

而二進位搜尋法在搜尋數值1~100，每次都是對半切，第一次搜尋50，若是太高，就搜尋1~49；若是太低，就搜尋51~100，不斷的對半切，直到找出數值。

實作程式

	'''
	演算法 | 二進位搜尋演算法---使用Python3
	https://hugheschung.blogspot.com/2019/01/python3.html
	'''
	def binary_search(list, item):
	low = 0
	high = len(list)-1 #len() 找出list中有多少個元素
	while low <= high:
	mid = round((low + high) / 2) # 找出中位數，並用round()四捨五入
	guess = list[mid]
	if guess == item:
	return mid
	if guess > item:
	high = mid - 1
	else:
	low = mid + 1
	return None
	my_list = [1,3,5,7,9]
	print(binary_search(my_list,3)) #印出在list中的位置
	print(binary_search(my_list,9)) #印出在list中的位置
	print(binary_search(my_list,2)) #印出在list中的位置

view raw 19P001_binary_search.py hosted with ❤ by GitHub

轉貼本文時，需註明來自黑修斯的隨手札記原創作者 hughes chen（黑修斯），及附上原文連結，同時 禁止修改，禁止商業使用 。