一、分塊查找算法
分塊查找是二分法查找和順序查找的改進方法，分塊查找要求索引表是有序的，對塊內結點沒有排序要求，塊內結點可以是有序的也可以是無序的。
分塊查找就是把一個大的線性表分解成若干塊，每塊中的節點可以任意存放，但塊與塊之間必須排序。與此同時，還要建立一個索引表，把每塊中的最大值作為索引表的索引值，此索引表需要按塊的順序存放到一個輔助數組中。查找時，首先在索引表中進行查找，確定要找的結點所在的塊。由于索引表是排序的，因此，對索引表的查找可以采用順序查找或二分查找；然后，在相應的塊中采用順序查找，即可找到對應的結點。
例如，有這樣一列數據：23、43、56、78、97、100、120、135、147、150。如下圖所示：
想要查找的數據是 150，使用分塊查找法步驟如下：
步驟1：將上圖所示的數據進行分塊，按照每塊長度為 4 進行分塊，分塊情況如下圖所示：
說明：每塊的長度是任意指定的，博主在這里用的長度為4，讀者可以根據自己的需要指定每塊長度。
步驟2：選取各塊中的最大關鍵字構成一個索引表，即選取上圖所示的各塊的最大值，第一塊最大的值是 78，第二塊最大的值是 135，第三塊最大值是 155，形成的索引表如下圖所示：
步驟3：用順序查找或者二分查找判斷想要查找數據 150 在上圖所示的索引表中的哪塊內容中，這里博主用的是二分查找法，即先取中間值 135 與 150 比較，如下圖所示：
步驟4：結果是中間位置的數據 135 比目標數據 150 小，因此目標數據在 135 的下一塊內。將數據定位在第 3 塊內，此時將第 3 塊內的數據取出，進行順序比較，如下圖所示：
步驟5：通過順序查找第 3 塊的內容，終于在第 9 個位置找到目標數，此時分塊查找結束。
總結：至此，分塊查找算法已經講解完畢。通過和二分查找法和順序查找法對比來看，分塊查找的速度雖然不如二分查找算法，但比順序查找算法快得多。當數據很多且塊數很大時，對索引表可以采用二分查找，這樣能夠進一步提高查找的速度。
二、實例：實現分塊查找算法
具體代碼如下：
def search(data, key): # 用二分查找 想要查找的數據在哪塊內
length = len(data) # 數據列表長度
first = 0 # 第一位數位置
last = length - 1 # 最后一個數據位置
print(f"長度:{length} 分塊的數據是:{data}") # 輸出分塊情況
while first = last:
mid = (last + first) // 2 # 取中間位置
if data[mid] > key: # 中間數據大于想要查的數據
last = mid - 1 # 將last的位置移到中間位置的前一位
elif data[mid] key: # 中間數據小于想要查的數據
first = mid + 1 # 將first的位置移到中間位置的后一位
else:
return mid # 返回中間位置
return False
# 分塊查找
def block(data, count, key): # 分塊查找數據，data是列表，count是每塊的長度，key是想要查找的數據
length = len(data) # 表示數據列表的長度
block_length = length // count # 一共分的幾塊
if count * block_length != length: # 每塊長度乘以分塊總數不等于數據總長度
block_length += 1 # 塊數加1
print("一共分", block_length, "塊") # 塊的多少
print("分塊情況如下：")
for block_i in range(block_length): # 遍歷每塊數據
block_data = [] # 每塊數據初始化
for i in range(count): # 遍歷每塊數據的位置
if block_i * count + i >= length: # 每塊長度要與數據長度比較，一旦大于數據長度
break # 就退出循環
block_data.append(data[block_i * count + i]) # 每塊長度要累加上一塊的長度
result = search(block_data, key) # 調用二分查找的值
if result != False: # 查找的結果不為False
return block_i * count + result # 就返回塊中的索引位置
return False
data = [23, 43, 56, 78, 97, 100, 120, 135, 147, 150, 155] # 數據列表
result = block(data, 4, 150) # 第二個參數是塊的長度，最后一個參數是要查找的元素
print("查找的值得索引位置是:", result) # 輸出結果
運行結果如下圖所示：
從上面的運行結果看到，當查找 150 時，查找結果完全符合上述描述的步驟。
到此這篇關于Python查找算法之分塊查找算法的實現的文章就介紹到這了,更多相關Python 分塊查找算法內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- Python實現在某個數組中查找一個值的算法示例
- Python中的二叉樹查找算法模塊使用指南
- Python實現二分查找算法實例
- python快速查找算法應用實例
- python二分查找算法的遞歸實現方法
- Python實現查找數組中任意第k大的數字算法示例
- python實現二分查找算法
- Python有序查找算法之二分法實例分析
- python有序查找算法 二分法實例解析
