快捷導(dǎo)航

Python查找算法之分塊查找算法的實(shí)現(xiàn)

更新時(shí)間：2021年04月08日 11:37:06 作者：Amo Xiang

這篇文章主要介紹了Python查找算法之分塊查找算法的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

一、分塊查找算法

分塊查找是二分法查找和順序查找的改進(jìn)方法，分塊查找要求索引表是有序的，對(duì)塊內(nèi)結(jié)點(diǎn)沒有排序要求，塊內(nèi)結(jié)點(diǎn)可以是有序的也可以是無(wú)序的。

分塊查找就是把一個(gè)大的線性表分解成若干塊，每塊中的節(jié)點(diǎn)可以任意存放，但塊與塊之間必須排序。與此同時(shí)，還要建立一個(gè)索引表，把每塊中的最大值作為索引表的索引值，此索引表需要按塊的順序存放到一個(gè)輔助數(shù)組中。查找時(shí)，首先在索引表中進(jìn)行查找，確定要找的結(jié)點(diǎn)所在的塊。由于索引表是排序的，因此，對(duì)索引表的查找可以采用順序查找或二分查找；然后，在相應(yīng)的塊中采用順序查找，即可找到對(duì)應(yīng)的結(jié)點(diǎn)。

例如，有這樣一列數(shù)據(jù)：23、43、56、78、97、100、120、135、147、150。如下圖所示：

在這里插入圖片描述

想要查找的數(shù)據(jù)是 150，使用分塊查找法步驟如下：

步驟1：將上圖所示的數(shù)據(jù)進(jìn)行分塊，按照每塊長(zhǎng)度為 4 進(jìn)行分塊，分塊情況如下圖所示：

在這里插入圖片描述

說明：每塊的長(zhǎng)度是任意指定的，博主在這里用的長(zhǎng)度為4，讀者可以根據(jù)自己的需要指定每塊長(zhǎng)度。

步驟2：選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，即選取上圖所示的各塊的最大值，第一塊最大的值是 78，第二塊最大的值是 135，第三塊最大值是 155，形成的索引表如下圖所示：

在這里插入圖片描述

步驟3：用順序查找或者二分查找判斷想要查找數(shù)據(jù) 150 在上圖所示的索引表中的哪塊內(nèi)容中，這里博主用的是二分查找法，即先取中間值 135 與 150 比較，如下圖所示：

在這里插入圖片描述

步驟4：結(jié)果是中間位置的數(shù)據(jù) 135 比目標(biāo)數(shù)據(jù) 150 小，因此目標(biāo)數(shù)據(jù)在 135 的下一塊內(nèi)。將數(shù)據(jù)定位在第 3 塊內(nèi)，此時(shí)將第 3 塊內(nèi)的數(shù)據(jù)取出，進(jìn)行順序比較，如下圖所示：

在這里插入圖片描述

步驟5：通過順序查找第 3 塊的內(nèi)容，終于在第 9 個(gè)位置找到目標(biāo)數(shù)，此時(shí)分塊查找結(jié)束。

總結(jié)：至此，分塊查找算法已經(jīng)講解完畢。通過和二分查找法和順序查找法對(duì)比來(lái)看，分塊查找的速度雖然不如二分查找算法，但比順序查找算法快得多。當(dāng)數(shù)據(jù)很多且塊數(shù)很大時(shí)，對(duì)索引表可以采用二分查找，這樣能夠進(jìn)一步提高查找的速度。

二、實(shí)例：實(shí)現(xiàn)分塊查找算法

具體代碼如下：

def search(data, key):  # 用二分查找 想要查找的數(shù)據(jù)在哪塊內(nèi)
    length = len(data)  # 數(shù)據(jù)列表長(zhǎng)度
    first = 0  # 第一位數(shù)位置
    last = length - 1  # 最后一個(gè)數(shù)據(jù)位置
    print(f"長(zhǎng)度:{length} 分塊的數(shù)據(jù)是:{data}")  # 輸出分塊情況
    while first <= last:
        mid = (last + first) // 2  # 取中間位置
        if data[mid] > key:  # 中間數(shù)據(jù)大于想要查的數(shù)據(jù)
            last = mid - 1  # 將last的位置移到中間位置的前一位
        elif data[mid] < key:  # 中間數(shù)據(jù)小于想要查的數(shù)據(jù)
            first = mid + 1  # 將first的位置移到中間位置的后一位
        else:
            return mid  # 返回中間位置
    return False


# 分塊查找
def block(data, count, key):  # 分塊查找數(shù)據(jù)，data是列表，count是每塊的長(zhǎng)度，key是想要查找的數(shù)據(jù)
    length = len(data)  # 表示數(shù)據(jù)列表的長(zhǎng)度
    block_length = length // count  # 一共分的幾塊
    if count * block_length != length:  # 每塊長(zhǎng)度乘以分塊總數(shù)不等于數(shù)據(jù)總長(zhǎng)度
        block_length += 1  # 塊數(shù)加1
    print("一共分", block_length, "塊")  # 塊的多少
    print("分塊情況如下：")
    for block_i in range(block_length):  # 遍歷每塊數(shù)據(jù)
        block_data = []  # 每塊數(shù)據(jù)初始化
        for i in range(count):  # 遍歷每塊數(shù)據(jù)的位置
            if block_i * count + i >= length:  # 每塊長(zhǎng)度要與數(shù)據(jù)長(zhǎng)度比較，一旦大于數(shù)據(jù)長(zhǎng)度
                break  # 就退出循環(huán)
            block_data.append(data[block_i * count + i])  # 每塊長(zhǎng)度要累加上一塊的長(zhǎng)度
        result = search(block_data, key)  # 調(diào)用二分查找的值
        if result != False:  # 查找的結(jié)果不為False
            return block_i * count + result  # 就返回塊中的索引位置
    return False


data = [23, 43, 56, 78, 97, 100, 120, 135, 147, 150, 155]  # 數(shù)據(jù)列表
result = block(data, 4, 150)  # 第二個(gè)參數(shù)是塊的長(zhǎng)度，最后一個(gè)參數(shù)是要查找的元素
print("查找的值得索引位置是:", result)  # 輸出結(jié)果

運(yùn)行結(jié)果如下圖所示：

在這里插入圖片描述