本文的最新版本位于：https://github.com/iwhales/algorithms_notes
轉(zhuǎn)載請注明出處：http://www.reibang.com/u/5e6f798c903a
參考：《數(shù)據(jù)結(jié)構(gòu)（Python 語言描述）》 - 3.3 搜索算法
學(xué)習(xí)思路按照以下三個層次推進：學(xué)習(xí)算法設(shè)計思路 >> 實現(xiàn)算法 >> 復(fù)雜度分析
Tips：為了保持簡潔，每個函數(shù)都只處理一個整數(shù)列表冈闭，并且假設(shè)列表不為空温亲。
1. 搜索最小值
Search for the Minimum
下面這個函數(shù)會返回列表中最小項的索引澎语，該算法的復(fù)雜度是 O(n) 药薯。
def index_of_min(lyst):
"""返回最小項的索引"""
min_index = 0
current_index = 1
while current_index < len(lyst):
if lyst[current_index] < lyst[min_index]:
min_index = current_index
current_index += 1
return min_index
2. 順序搜索
順序搜索(Sequential Search)吉懊，也稱線性搜索(linear search)刽脖。
如果需要在對象上使用 in 進行成員測試盆繁，則需要為該對象實現(xiàn) __contains__() 方法肾胯。如果對象中包含指定項竖席，返回 True；否則返回 False 敬肚。下面這個順序搜索函數(shù)毕荐，實現(xiàn)了與列表中 __contains__() 方法類的功能。
def sequential_search(target, lyst):
"""如果找到目標(biāo)項艳馒，返回其索引憎亚；否則返回-1"""
position = 0
while position < len(lyst):
if target == lyst[position]:
return position
position += 1
return -1
2.1 最好情況员寇、最壞情況、平均情況
Best-Case, Worst-Case, and Average-Case Performance Revisited
有些算法的性能與數(shù)據(jù)的排列方式有關(guān)第美，比如順序搜索算法蝶锋。此時，我們可以分三種情況考慮考慮該算法的性能：
- 最壞情況：對于"順序搜索"而言什往，在最壞情況下扳缕，目標(biāo)項位于列表末尾，或根本不在列表之中别威。此時必須訪問列表中的每一項躯舔，對大小為 n 的列表要執(zhí)行 n 次迭代。因此省古，順序搜索在最壞的情況下復(fù)雜度為 O(n) 粥庄。
- 最好情況："順序搜索"只進行一次迭代就在第一個位置找到了目標(biāo)項，復(fù)雜度為 O(1) 豺妓。
- 平均情況：需要把從"最好情況"到"最壞情況"間可能出現(xiàn)的所有情況的迭代次數(shù)相加惜互，并除以 n。因此琳拭，算法平均執(zhí)行了 (1+2+3+...+n-1+n)/n 次迭代训堆，化簡后等于 (n+1)/2 。對于很大的 n 而言臀栈，常數(shù)因子 2 的作用并不大蔫慧。因此，平均情況的復(fù)雜度仍然為 O(n) 权薯。
3. 二叉搜索
Binary Search
二叉搜索也稱二分查找姑躲，該算法針對有序列表，其時間復(fù)雜度是 O(\log_{2}n) 盟蚣。
假設(shè)我們需要利用二叉搜索查找某個按照升序排列的列表黍析。首先，二叉算法會找出位于列表中間位置的中間項屎开，并將該項與目標(biāo)項進行比較：如果兩者一致阐枣，便返回中間項的索引；如果目標(biāo)項小于中間項奄抽，則繼續(xù)搜索列表的前半部分蔼两；反之，則搜索后半部分逞度。當(dāng)找到目標(biāo)额划，或當(dāng)索引的起點值大于終點值時停止搜索。
注意档泽，使用二叉搜索時有一個額外的整體性代價俊戳，就是必須保持列表的有序性揖赴。
下面分別使用"循環(huán)方式"和"遞歸方式"來實現(xiàn)二叉搜索。
3.1 循環(huán)方式
# -*- coding: utf-8 -*-
def binary_search_loop(sorted_list: list, target: int):
"""
二分查找抑胎，循環(huán)方式
:param sorted_list: 按升序排列的列表
:param target: 被查找的目標(biāo)項
:return: 如果sorted_list中包含target燥滑，返回target的索引值，否則返回None
"""
low = 0
high = len(sorted_list) - 1
while low <= high:
mid_point = (low + high) // 2
if sorted_list[mid_point] == target:
return mid_point
elif sorted_list[mid_point] > target:
high = mid_point - 1
else:
low = mid_point + 1
return None
if __name__ == '__main__':
my_list = [1, 2, 3, 4]
assert binary_search_loop(my_list, 1) == 1
assert binary_search_loop(my_list, 2) == 1
assert binary_search_loop(my_list, 3) == 2
assert binary_search_loop(my_list, 4) == 3
assert binary_search_loop(my_list, 10) is None
3.2 遞歸方式
- 基線條件：數(shù)組只包含一個元素阿逃，如果目標(biāo)值與該元素相同铭拧，便在最終的基線條件下找到了目標(biāo)值，否則目標(biāo)值不在數(shù)組中恃锉。
- 遞歸條件：每次把數(shù)組分成兩半羽历，并丟棄其中的一半，對剩下的一半再次執(zhí)行二分查找淡喜。
# -*- coding: utf-8 -*-
def binary_search_recursive(sorted_list: list, target: int):
"""
二分查找，遞歸方式
:param sorted_list: 按升序排列的列表
:param target: 被查找的目標(biāo)項
:return: 如果sorted_list中包含target诵闭，返回target的索引值炼团，否則返回None
"""
mid = (len(sorted_list) - 1) // 2
if len(sorted_list) == 1: # 基線條件
if target == sorted_list[0]:
return 0
else:
return None
elif target == sorted_list[mid]: # 基線條件
return mid
# 下面的代碼，通過遞歸逐步縮減問題規(guī)模
if target > sorted_list[mid]:
index = binary_search_recursive(sorted_list[mid + 1:], target)
if index is None:
return None
# 減半后的新列表sorted_list[mid + 1:]會重新以索引0開頭蛤签，
# 這里需要保證返回的索引值包含當(dāng)前sorted_list列表的索引信息弟头，
# 因此需要重新調(diào)整index中的索引值俱笛。
# 要將index中的索引值調(diào)整到sorted_list列表中的對應(yīng)位置，
# 需要為index加上(mid + 1)
return index + (mid + 1)
else:
index = binary_search_recursive(sorted_list[:mid], target)
return index
if __name__ == '__main__':
assert binary_search_recursive(my_list, 1) == 0
assert binary_search_recursive(my_list, 2) == 1
assert binary_search_recursive(my_list, 3) == 2
assert binary_search_recursive(my_list, 4) == 3
assert binary_search_recursive(my_list, 10) is None
3.3 最壞情況
當(dāng)目標(biāo)項不在列表中的時候锌俱，便會出現(xiàn)最壞情況。在最壞情況下敌呈，對于大小為 n 的列表贸宏，會持續(xù)將列表長度除以 2，直至商為 1 時停止(如磕洪， n//2//...//2 = 1 )——其中除法執(zhí)行的次數(shù)便是循環(huán)執(zhí)行的總次數(shù)吭练。假設(shè)除法執(zhí)行的次數(shù)為 k ，那么便有 n/2^k=1 析显，可得 k=log_2n 鲫咽。因此，二叉搜索最壞情況的復(fù)雜度為 O(log_2n) 谷异。
下圖展示了在僅含 1~9 的整數(shù)列表中分尸，用二叉搜索查找整數(shù) 10 的過程〈踵冢灰色項表示中間項箩绍，用于和目標(biāo)項進行比較，也就是會被訪問的項荞下。另外伶选，位于初始列表前半部分的項史飞，實際上并不會被訪問。
