python數據結構之搜索講解
往期學習：
python數據類型: python數據結構：數據類型.
python的輸入輸出: python數據結構之輸入輸出及控制和異常.
python面向對象: python數據結構面向對象.
python算法分析: python數據結構之算法分析.
python棧、隊列和雙端隊列:python數據結構棧、隊列和雙端隊列.
python遞歸: python數據結構之遞歸.
上一期講的遞歸，對於初學者其實是不太友好的，遞歸需要自己多去接觸，自己多畫畫圖，這樣可以加強理解遞歸的過程，本期我們要講的內容是搜索，也可以叫查找。我將講解幾種最為普遍的查找算法。
1. 普通搜索
搜索是指從元素集合中找到某個特定元素的算法過程。搜索過程通常返回 True 或 False， 分別表示元素是否存在。
python中提供瞭 in 方法可以判斷元素是否存在列表中：
# python提供in函數進行搜索 a=[3,4,5,8,'t'] 't' in a 9 in a
結果如下：
2. 順序搜索
順序搜索故名思義：從列表中的第一個元素開始，沿著默認的順序逐個查看， 直到找到目標元素或者查完列表。如果查完列表後仍沒有找到目標元素，則說明目標元素不在列表中。
順序搜索過程：
1.1 無序下的順序查找
無序下的順序搜索很有特點，列表無序，隻好一個一個去比較，尋找元素。
#順序查找
def sequentialsearch(testlist,item):
pos=0
found=False
while pos<len(testlist) and not found:
if testlist[pos]==item:
found=True
else:
pos=pos+1
return found
結果如下：
分析一下這種順序查找，這種查找方式，最好的方式就尋找一次就成功瞭，最壞的情況的需要查找n次，於是時間復雜度是O(n)
1.2 有序下的順序查找
有序下的順序查找就是所查找的列表是有序的，
# 有序下的順序搜索
def ordersearch(testlist,item):
pos=0
found=False
stop=False
while pos<len(testlist) and not found and not stop:
if testlist[pos]==item:
found=True
else:
if testlist[pos]>item:
stop=True
else:
pos=pos+1
return found
結果如下：
分析一下這種搜索方法，正常情況下來說，最好情況下，搜索1次就能成功，最差情況隻需要n/2次即可搜索完成，但時間復雜度依舊是O(n)，隻有當列表中不存在目標元素時，有序排列的元素才會提高順序搜索的效率。
2.二分查找
二分查找：是利用列表有序的這個原理，從中間的元素著手。如果這個元素就是目標元素，那就立即停止搜索；如果不是，則可以利用列表有序的特性，排除一半的元素。如果目標元素比中間的元素大，就可以直接排除列表的左半部分和中間的元素。這是因為，如果列表包含目標元素，它必定位於右半部分。
在有序整數列表中進行二分搜索：
二分查找實現方式：
def binarysearch(testlist,item):
testlist.sort()#排序
left=0#左指針
right=len(testlist)-1#右指針
found=False
while left<=right and not found:
mid=(left+right)//2#取中間值
if testlist[mid]==item:
found=True
else:
if testlist[mid]<item:
left=mid+1
else:
right=mid-1
return found
看看效果：
二分查找遞歸實現：
def binarysearch2(testlist,item):
if len(testlist) == 0:
return False
else:
mid = len(testlist) // 2
if testlist[mid] == item:
return True
else:
if item < testlist[mid]:
return binarysearch2(testlist[:mid], item)
else:
return binarysearch2(testlist[mid+1:], item)
看看效果：
總結一下二分查找：在進行二分搜索時，每一次比較都將待考慮的元素減半，。那麼，要檢查完整個列表，二分搜索算法最多要比較多少次呢？假設列表共有 n 個元素，第一次比較後剩下n 個元素，第 2 次比較2後剩下n /4個元素，接下來是n/8 ，然後是n/16 ，依此類推。列表能拆分多少次？
二分搜索算法的表格分：
3.散列查找
散列查找：通過散列構建一個時間復雜度為 O(1)的數據結構。我們平常聽的最多哈希表就是散列的一種方式。
散列表：散列表是元素集合，其中的元素以一種便於查找的方式存儲。散列表中的每個位置通常被稱 為槽，其中可以存儲一個元素。槽用一個從 0 開始的整數標記，例如 0 號槽、1 號槽、2 號槽， 等等。初始情形下，散列表中沒有元素，每個槽都是空的。可以用列表來實現散列表，並將每個元素都初始化為 Python 中的特殊值 None。下圖展示瞭大小 m 為 11 的散列表。也就是說，表中有 m 個槽，編號從 0 到 10。
有11 個槽的散列表：
：
散列函數:將散列表中的元素與其所屬位置對應起來。對散列表中的任一元素，散列函數返回 一個介於 0 和 m – 1 之間的整數。假設有一個由整數元素 54、26、93、17、77 和 31 構成的集 合。首先來看第一個散列函數，它有時被稱作“取餘函數”，即用一個元素除以表的大小，並將 得到的餘數作為散列值（h(item) = item%11）。下圖給出瞭所有示例元素的散列值。取餘函數是一個很常見的散列函數，這是因為結果必須在槽編號范圍內。
使用餘數作為散列值：
計算出散列值後，就可以將每個元素插入到相應的位置，如圖 5-5 所示。註意，在 11 個槽 中，有 6 個被占用瞭。占用率被稱作載荷因子，記作λ \lambdaλ，定義如下：
有 6 個元素的散列表：
3.1 幾種散列函數
給定一個元素集合，能將每個元素映射到不同的槽，這種散列函數稱作完美散列函數。如果元素已知，並且集合不變，那麼構建完美散列函數是可能的。不幸的是，給定任意一個元素集合，沒有系統化方法來保證散列函數是完美的。所幸，不完美的散列函數也能有不錯的性能。
- 折疊法：先將元素切成等長的部分（最後一部分的長度可能不同），然後將這些部分相加，得到散列值。假設元素是電話號碼 436-555-4601，以 2 位為一組進行切分，得到 43、65、55、46 和 01。將這些數字相加後，得到 210。
- 平方取中法：先將元素取平方，然後提取中間幾位數。如果元素是 44，先計算 442=1936，然後提取中間兩位 93，繼續進行取餘的步驟。
- 字符編碼：采用python中的ord函數將單詞“cat”看作序數值序列，再將這些序數值相加，並采用取餘法得到散列值。
3.2 處理散列表沖突
完美的散列表，一個元素隻對應著一個卡槽，可是如果當2個元素被分配到一個卡槽時，必須通過一種系統化方法在散列表中安置第二個元素。這個過程被稱為處理沖突。
開發定址法：在散列表中找到另一個空槽，用於放置引起沖突的元素。簡單的做法是從起初的散列值開始，順序遍歷散列表，直到找到一個空槽。註意，為瞭遍歷散列表，可能需要往回檢查第一個槽。（例如：將（54, 26, 93, 17, 77, 31, 44, 55, 20）放入卡槽中。）
再散列：采用“加 3”探測策略處理沖突後的元素分佈情況。發生沖突時，為瞭找到空槽，該策略每次跳兩個槽。
平方探測：線性探測的一個變體，它不采用固定的跨步大小，而是通過再散列函數遞增散列 值。如果第一個散列值是 h，後續的散列值就是 h+1、h+4、h+9、h+16，等等。換句話說，平方探測的跨步大小是一系列完全平方。
鏈接法：允許散列 表中的同一個位置上存在多個元素。發生沖突時，元素仍然被插入其散列值對應的槽中。不過， 隨著同一個位置上的元素越來越多，搜索變得越來越困難。
3.3 散列表的實現（加1重復）
哈希散列的實現：
#哈希表
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self, key, data):
hashvalue = self.hashfunction(key, len(self.slots))
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data #替換
else:
nextslot = self.rehash(hashvalue, len(self.slots))
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot, len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot] = key
self.data[nextslot] = data
else:
self.data[nextslot] = data #替換
def hashfunction(self, key, size):
return key%size
def rehash(self, oldhash, size):
return (oldhash + 1)%size
#get函數
def get(self, key):
startslot = self.hashfunction(key, len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position, len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
結果如下：
我們分析一下散列查找：在最好情況下，散列搜索算法的時間復雜度是 O(1)，即常數階。但可能發生沖突，所以比較次數通常不會這麼簡單。
4.參考資料
- 《python數據結構與算法》
- 《大話數據結構》
到此這篇關於python數據結構之搜索講解的文章就介紹到這瞭,更多相關python搜索講解內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- Redis字典實現、Hash鍵沖突及漸進式rehash詳解
- python數據結構之棧、隊列及雙端隊列
- python 基於pygame實現俄羅斯方塊
- python pygame實現控制物體移動
- Python雙端隊列實現回文檢測