Python 語言實(shí)現(xiàn)六大查找算法

一、順序查找算法

順序查找又稱為線性查找，是最簡單的查找算法。這種算法就是按照數(shù)據(jù)的順序一項(xiàng)一項(xiàng)逐個查找，所以不管數(shù)據(jù)順序如何，都得從頭到尾地遍歷一次。順序查找的優(yōu)點(diǎn)就是數(shù)據(jù)在查找前，不需要對其進(jìn)行任何處理(包括排序)。缺點(diǎn)是查找速度慢，如果數(shù)據(jù)列的第一個數(shù)據(jù)就是想要查找的數(shù)據(jù)，則該算法查找速度為最快，只需查找一次即可；如果查找的數(shù)據(jù)是數(shù)據(jù)列的最后一個(第幾個)，則該算法查找速度為最慢，需要查找 n 次，甚至還會出現(xiàn)未找到數(shù)據(jù)的情況。

例如，有這樣一組數(shù)據(jù)：10、27、13、14、19、85、70、29、69、27。如果想要查找數(shù)據(jù) 19，需要進(jìn)行 5 次查找；如果想要查找數(shù)據(jù) 27，需要進(jìn)行 10 次查找；如果想要查找數(shù)據(jù) 10，只需要進(jìn)行 1 次查找。

從這個例子中可以看出，當(dāng)查找的數(shù)據(jù)較多時，用順序查找就不太合適，所以說順序查找只能應(yīng)用于查找數(shù)據(jù)較少的數(shù)據(jù)列。這個過程好比我們在抽屜里找筆，如下圖所示。通常情況下我們會從上層的抽屜開始，一層一層地查找，直到找到筆為止，這個例子就是生活中典型的順序查找算法。

例如，隨機(jī)從 1~100 之間生成 50 個整數(shù)，并將隨機(jī)生成的這 50 個數(shù)顯示出來，然后用順序查找算法查找16、45、97這幾個數(shù)據(jù)的位置。具體代碼如下：

import random  # 導(dǎo)入隨機(jī)數(shù)模塊

num = 0  # 定義變量num
# 使用列表推導(dǎo)式生成包含50個元素的列表
data = [random.randint(1, 100) for i in range(50)]
print("隨機(jī)產(chǎn)生的數(shù)據(jù)內(nèi)容是：")
for i in range(10):  # 遍歷行
    for j in range(5):  # 遍歷列
        # 按格式輸出隨機(jī)生成內(nèi)容
        print('%2d[%3d] ' % (i * 5 + j + 1, data[i * 5 + j]), end='')
    print('')
while num != -1:  # 循環(huán)輸入
    find = 0  # 比較次數(shù)
    num = int(input("請輸入想要查找的數(shù)據(jù)，輸入-1退出程序:"))  # 數(shù)據(jù)輸入
    for i in range(50):  # 循環(huán)遍歷50個隨機(jī)數(shù)
        if data[i] == num:  # 判斷輸入數(shù)據(jù)和data數(shù)據(jù)是否相等
            print("在", i + 1, "個位置找到數(shù)據(jù)", data[i])  # 輸出找到的位置和數(shù)據(jù)內(nèi)容
            find += 1  # 比較次數(shù)加1
    if find == 0 and num != -1:  # 判斷比較次數(shù)是否為0且輸入數(shù)據(jù)是否為-1
        print("沒有找到", num, "此數(shù)據(jù)")  # 提示沒有找到數(shù)據(jù)

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

二、折半查找算法

折半查找算法又稱為二分查找算法，折半查找算法是將數(shù)據(jù)分割成兩等份，首先用鍵值(要查找的數(shù)據(jù))與中間值進(jìn)行比較。如果鍵值小于中間值，可確定要查找的鍵值在前半段；如果鍵值大于中間值，可確定要查找的鍵值在后半段。然后對前半段(后半段)進(jìn)行分割，將其分成兩等份，再對比鍵值。如此循環(huán)比較、分割，直到找到數(shù)據(jù)或者確定數(shù)據(jù)不存在為止。折半查找的缺點(diǎn)是只適用于已經(jīng)初步排序好的數(shù)列；優(yōu)點(diǎn)是查找速度快。

生活中也有類似于折半查找的例子，例如，猜數(shù)字游戲。在游戲開始之前，首先會給出一定的數(shù)字范圍(例如0~100)，并在這個范圍內(nèi)選擇一個數(shù)字作為需要被猜的數(shù)字。然后讓用戶去猜，并根據(jù)用戶猜的數(shù)字給出提示(如猜大了或猜小了)。用戶通常的做法就是先在大范圍內(nèi)隨意說一個數(shù)字，然后提示猜大了/猜小了，這樣就縮小了猜數(shù)字的范圍，慢慢地就猜到了正確的數(shù)字，如下圖所示。這種做法與折半查找法類似，都是通過不斷縮小數(shù)字范圍來確定數(shù)字，如果每次猜的范圍值都是區(qū)間的中間值，就是折半查找算法了。

例如，已經(jīng)有 排序好 的數(shù)列：12、45、56、66、77、80、97、101、120，要查找的數(shù)據(jù)是 101，用折半查找步驟如下：

步驟1：將數(shù)據(jù)列出來并找到中間值 77，將 101 與 77 進(jìn)行比較，如下圖所示。

步驟2：將 101 與 77 進(jìn)行比較，結(jié)果是 101 大于 77，說明要查找的數(shù)據(jù)在數(shù)列的右半段。此時不考慮左半段的數(shù)據(jù)，對在右半段的數(shù)據(jù)再進(jìn)行分割，找中間值。這次中間值的位置在 97 和 101 之間，取 97，將 101 與 97 進(jìn)行比較，如下圖所示。

步驟3：將 101 與 97 進(jìn)行比較，結(jié)果是 101 大于 97，說明要查找的數(shù)據(jù)在右半段數(shù)列中，此時不考慮左半段的數(shù)據(jù)，再對剩下的數(shù)列分割，找中間值，這次中間值位置是 101，將 101 與 101 進(jìn)行比較，如下圖所示。

步驟4：將 101 與 101 進(jìn)行比較，所得結(jié)果相等，查找完成。說明：如果多次分割之后沒有找到相等的值，表示這個鍵值沒有在這個數(shù)列中。

從折半法查找的步驟來看，明顯比順序查找法的次數(shù)少，這就是折半查找法的優(yōu)點(diǎn)：查找速度快。

有一條的150米線路，在這條線路上存在故障。第一天維修工已經(jīng)大致鎖定了幾個疑似故障點(diǎn)，疑似故障點(diǎn)分別在線路的12、45、56、66、77、80、97、101、120米處。第二天維修工要在這9個疑似故障點(diǎn)中確定一個真正的故障點(diǎn)（假設(shè)真正的故障點(diǎn)是101米處）。維修工為了快速查找此故障點(diǎn)，就在每段數(shù)據(jù)的中間位置開始排查。

例如，第一次選擇在77米處的疑似故障點(diǎn)接通電路，發(fā)現(xiàn)接通，他判斷此故障在77米之后的位置；第二次取97米處的疑似故障點(diǎn)，發(fā)現(xiàn)也接通了，說明在97米之后的位置；第三次取101米處的位置，再次接通線路，發(fā)現(xiàn)未接通，說明此處是真正的故障點(diǎn)。此次查找經(jīng)歷了3次，將真正故障點(diǎn)找到。具體代碼如下：

def search(data, num):
    """
    定義查找函數(shù)：該函數(shù)使用的是折半查找算法
    :param data: 原數(shù)列data
    :param num: 鍵值num
    :return:
    """
    low = 0  # 定義變量用來表示低位
    high = len(data) - 1  # 定義變量用來表示高位
    print("正在查找.......")  # 提示
    while low = high and num != -1:
        mid = int((low + high) / 2)  # 取中間位置
        if num  data[mid]:  # 判斷數(shù)據(jù)是否小于中間值
            # 輸出位置在數(shù)列中的左半邊
            print(f"{num} 介于中間故障點(diǎn) {low + 1}[{data[low]}] 和故障點(diǎn)位置 {mid + 1}[{data[mid]}] 之間，找左半邊......")
            high = mid - 1  # 最高位變成了中間位置減1
        elif num > data[mid]:  # 判斷數(shù)據(jù)是否大于中間值
            # 輸出位置在數(shù)列中的右半邊
            print(f"{num} 介于中間故障點(diǎn) {mid + 1}[{data[mid]}] 和故障點(diǎn)位置 {high + 1}[{data[high]}] 之間，找右半邊......")
            low = mid + 1  # 最低位變成了中間位置加1
        else:  # 判斷數(shù)據(jù)是否等于中間值
            return mid  # 返回中間位置
    return -1  # 自定義函數(shù)到此結(jié)束


inp_num = 0  # 定義變量，用來輸入鍵值
num_list = [12, 45, 56, 66, 77, 80, 97, 101, 120]  # 定義數(shù)列
print("疑似故障點(diǎn)如下：")
for index, ele in enumerate(num_list):
    print(f" {index + 1}[{ele}]", end="")  # 輸出數(shù)列
print("")
flag = True  # 開關(guān)，用來管控是否多次查找

while flag:  # 循環(huán)查找
    inp_num = int(input("請輸入故障點(diǎn)：").strip())  # 輸入查找鍵值
    if inp_num == -1:  # 判斷鍵值是否是-1
        break  # 若為-1，跳出循環(huán) 即結(jié)束程序
    result = search(num_list, inp_num)  # 調(diào)用自定義的查找函數(shù)——search()函數(shù)
    if result == -1:  # 判斷查找結(jié)果是否是-1
        print(f"沒有找到[{inp_num}]故障點(diǎn)")  # 若為-1，提示沒有找到值
    else:
        # 若不為-1，提示查找位置
        print(f"在{result + 1}個位置找到[{num_list[result]}]故障點(diǎn)")
    char = input("本次查找結(jié)束，是否繼續(xù)查找，請輸入 y(Y) 或 n(N)：").strip()
    if char.upper() == "N":
        flag = False

程序執(zhí)行結(jié)果如下圖所示：

三、插補(bǔ)查找算法

插補(bǔ)查找算法又稱為插值查找，它是折半查找算法的改進(jìn)版。插補(bǔ)查找是按照數(shù)據(jù)的分布，利用公式預(yù)測鍵值所在的位置，快速縮小鍵值所在序列的范圍，慢慢逼近，直到查找到數(shù)據(jù)為止。根據(jù)描述來看，插值查找類似于平常查英文字典的方法。例如，在查一個以字母 D 開頭的英文單詞時，決不會用折半查找法。根據(jù)英文詞典的查找順序可知，D 開頭的單詞應(yīng)該在字典較前的部分，因此可以從字典前部的某處開始查找。鍵值的索引計(jì)算，公式如下：

middle=left+(target-data[left])/(data[right]-data[left])*(right-left)

參數(shù)說明：

1. middle：所求的邊界索引。
2. left：最左側(cè)數(shù)據(jù)的索引。
3. target：鍵值(目標(biāo)數(shù)據(jù))。
4. data[left]：最左側(cè)數(shù)據(jù)值。
5. data[right]：最右側(cè)數(shù)據(jù)值。
6. right：最右側(cè)數(shù)據(jù)的索引。

例如，已經(jīng)有排序好的數(shù)列：34、53、57、68、72、81、89、93、99。要查找的數(shù)據(jù)是 53，使用插補(bǔ)查找法步驟如下：

步驟1：將數(shù)據(jù)列出來并利用公式找到邊界值，計(jì)算過程如下：

將各項(xiàng)數(shù)據(jù)帶入公式：

將數(shù)據(jù)取整，因此所求索引是 2，對應(yīng)的數(shù)據(jù)是 57，將查找目標(biāo)數(shù)據(jù) 53 與 57 進(jìn)行比較，如下圖所示。

步驟2：將 53 與 57 進(jìn)行比較，結(jié)果是 53 小于 57，所以查找 57 的左半邊數(shù)據(jù)，不用考慮右半邊的數(shù)據(jù)，索引范圍縮小到 0 和 2 之間，公式帶入：

取整之后索引是 1，對應(yīng)的數(shù)據(jù)是 53，將查找目標(biāo)數(shù)據(jù) 53 與 53 進(jìn)行比較，如下圖所示：

步驟3：將 53 與 53 進(jìn)行比較，所得結(jié)果相等，查找完成。說明：如果多次分割之后沒有找到相等的值，表示這個鍵值沒有在這個數(shù)列中。

通過上述的步驟1就能看出，插補(bǔ)查找算法比折半查找算法的取值范圍更小，因此它的速度要比折半法查找快，這就是插補(bǔ)查找算法的優(yōu)點(diǎn)。

用戶可以隨意輸入一組數(shù)據(jù)，例如本實(shí)例輸入一組數(shù)據(jù)：34、53、57、68、72、81、89、93、99。在這組數(shù)據(jù)中用插補(bǔ)查找法分別查找數(shù)據(jù) 57、53、93、89、100，且顯示每次查找的過程。用 Python 代碼實(shí)現(xiàn)此過程，具體代碼如下：

def insert_search(data, num):
    """
    自定義查找函數(shù)：該函數(shù)使用的是插補(bǔ)查找算法
    :param data: 原數(shù)列data
    :param num: 鍵值num
    :return:
    """
    # 計(jì)算
    left_index = 0  # 最左側(cè)數(shù)據(jù)的索引
    right_index = len(data) - 1  # 最右側(cè)數(shù)據(jù)的索引
    print("正在查找.......")  # 提示
    while left_index = right_index:
        # 使用公式計(jì)算出索引值
        middle = left_index + (num - data[left_index]) / (data[right_index] - data[left_index]) * (
                right_index - left_index)
        # 取整
        middle = int(middle)
        # print(middle)
        if num == data[middle]:
            return middle  # 如果鍵值等于邊界值，返回邊界位置
        elif num  data[middle]:
            # 輸出位置在數(shù)列中的左半邊
            print(f"{num} 介于位置{left_index + 1}[{data[left_index]}]和邊界值{middle + 1}[{data[middle]}]之間，找左半邊......")
            right_index = middle - 1  # 如果鍵值小于邊界值，最右邊數(shù)據(jù)索引等于邊界位置減1
        else:
            # 輸出位置在數(shù)列中的左半邊
            print(f"{num} 介于位置{middle + 1}[{data[middle]}]和邊界值{right_index + 1}[{data[right_index]}]之間，找右半邊......")
            left_index = middle + 1  # 如果鍵值大于邊界值，最左邊數(shù)據(jù)索引等于邊界位置加1
    return -1  # 自定義函數(shù)到此結(jié)束

inp_num = 0  # 定義變量，用來輸入鍵值
num_list = [34, 53, 57, 68, 72, 81, 89, 93, 99]  # 定義數(shù)列
print("數(shù)據(jù)內(nèi)容是：")
for index, ele in enumerate(num_list):
    print(f" {index + 1}[{ele}]", end="")  # 輸出數(shù)列
print("")
flag = True  # 開關(guān)，用來管控是否多次查找

while flag:  # 循環(huán)查找
    inp_num = int(input("請輸入要查找的鍵值：").strip())  # 輸入查找鍵值
    result = insert_search(num_list, inp_num)  # 調(diào)用自定義的查找函數(shù)——insert_search()函數(shù)
    if result == -1:  # 判斷查找結(jié)果是否是-1
        print(f"沒有找到[{inp_num}]")  # 若為-1，提示沒有找到值
    else:
        # 若不為-1，提示查找位置
        print(f"在{result + 1}個位置找到[{inp_num}]")
    char = input("本次查找結(jié)束，是否繼續(xù)查找，請輸入 y(Y) 或 n(N)：").strip()
    if char.upper() == "N":
        flag = False

程序執(zhí)行結(jié)果如下圖所示：

四、哈希查找算法

哈希查找算法是使用哈希函數(shù)來計(jì)算一個鍵值所對應(yīng)的地址，進(jìn)而建立哈希表格，然后利用哈希函數(shù)來查找到各個鍵值存放在表格中的地址。簡單來說，就是把一些復(fù)雜的數(shù)據(jù)，通過某種函數(shù)映射(與數(shù)學(xué)中的映射概念一樣)關(guān)系，映射成更加易于查找的方式。哈希查找算法的查找速度與數(shù)據(jù)多少無關(guān)，完美的哈希查找算法一般都可以做到一次讀取完成查找。

就像生活中，要想找到自己想要的物品，最好的辦法就是把該物品固定在某個地方，每次需要用到它的時候就去對應(yīng)的地方找，用完之后再放回原處。哈希查找法就是這樣的一種算法，例如，在一本書中查找內(nèi)容，首先翻開這本書的目錄，然后在目錄上找到想要的內(nèi)容，最后直接根據(jù)對應(yīng)的頁碼就能找到所需要的內(nèi)容。

哈希查找算法具有保密性高的特點(diǎn)，因此哈希查找算法常被應(yīng)用在數(shù)據(jù)壓縮和加解密方面。常見的哈希算法有除留取余法、平方取中法以及折疊法。在講解這三種算法之前，首先需要了解 哈希表 和 哈希函數(shù) 的概念。

1. 哈希表和哈希函數(shù)

哈希表是存儲鍵值和鍵值所對應(yīng)地址的一種數(shù)據(jù)集合。哈希表中的位置，一般稱為槽位，每個槽位都能保存一個數(shù)據(jù)元素并以一個整數(shù)命名(從 0 開始)。這樣我們就有了0號槽位、1號槽位等。起始時，哈希表里沒有數(shù)據(jù)，槽位是空的，這樣在構(gòu)建哈希表時，可以把槽位的值都初始化成 None，如下圖所示。

這是一個大小為 11 的哈希表，或者說有 n 個槽位的哈希表，n 為0~10。上圖中的元素和保存的槽位之間的映射關(guān)系，稱為哈希函數(shù)。哈希函數(shù)接受一個元素作為參數(shù)，返回一個0到n-1的整數(shù)作為槽位名。說明：每種哈希算法的哈希函數(shù)和哈希表，會在每種哈希算法中介紹。

2. 除留余數(shù)法

除留余數(shù)法是哈希算法中最簡單的一種算法。它是將每個數(shù)據(jù)除以某個常數(shù)后，取余數(shù)來當(dāng)索引。除留取余法所對應(yīng)的哈希函數(shù)形式如下：

h(item)=item % num

參數(shù)說明：

• item：每個數(shù)據(jù)。
• num：一個常數(shù)，一般會選擇一個質(zhì)數(shù)，如下面的例子中取質(zhì)數(shù) 11。

例如，將整數(shù)集：54、26、93、17、77、31 中每個數(shù)據(jù)都除以 11，所得的余數(shù)作為哈希值，哈希值如下表所示。

注意：除留余數(shù)法一般以某種形式存于所有哈希函數(shù)中，因?yàn)樗倪\(yùn)算結(jié)果一定在槽位范圍內(nèi)。哈希值計(jì)算出來之后，就要把元素插入到哈希表中指定的位置，如下圖所示。

則對應(yīng)的哈希函數(shù)也得到了哈希值，如：h(54)=10，h(26)=4，h(93)=5，h(17)=6，h(77)=0，h(31)=9。

3. 折疊法

對給定的數(shù)據(jù)集，哈希函數(shù)將每個元素映射為單個槽位，稱為 完美哈希函數(shù)。但是對于任意一個數(shù)據(jù)集合，沒有系統(tǒng)能構(gòu)造出完美哈希函數(shù)。例如，在上述除留余數(shù)法的例子中再加上一個數(shù)據(jù) 44，該數(shù)字除以 11 后，得到的余數(shù)是 0，這與數(shù)據(jù) 77 的哈希值相同。遇到這種情況時，解決辦法之一就是擴(kuò)大哈希表，但是這種做法太浪費(fèi)空間。因此又有了擴(kuò)展除留取余數(shù)的方案，也就是折疊法。

折疊法是將數(shù)據(jù)分成一串?dāng)?shù)據(jù)，先將數(shù)據(jù)拆成幾部分，再把它們加起來作為哈希地址。例如，有這樣一串?dāng)?shù)據(jù)：5205211314，將這串?dāng)?shù)據(jù)中的數(shù)字兩兩分一組，如下圖所示：

然后將拆的數(shù)據(jù)進(jìn)行相加，如下圖所示：

相加之后得到的數(shù)值就是這串?dāng)?shù)據(jù)的哈希地址，如果設(shè)定槽位是 11，用除留余數(shù)法將哈希地址除以 11，得到的值是 6，而數(shù)據(jù) 6 就是這串?dāng)?shù)據(jù)的哈希值，這種做法稱為 移動折疊法。

有些折疊法多了一步，就是在相加之前，對數(shù)據(jù)進(jìn)行奇數(shù)或偶數(shù)反轉(zhuǎn)，再將反轉(zhuǎn)后的數(shù)字相加。下圖所示就是將奇數(shù)反轉(zhuǎn)的過程，再將反轉(zhuǎn)后的數(shù)據(jù)相加，得到的 159 也稱為哈希地址。

此時設(shè)定槽位是 11，將哈希地址除以 11，得到的值是 5，數(shù)據(jù) 5 就是這個數(shù)據(jù)的哈希值。接下來介紹將偶數(shù)反轉(zhuǎn)的情況，如下圖所示。

將上圖中反轉(zhuǎn)后的數(shù)據(jù)相加，得到的 105 也稱為哈希地址。如果設(shè)定槽位是 11，除留余數(shù)法將哈希地址除以 11，得到的值是 6，數(shù)據(jù) 6 就是這個數(shù)據(jù)的哈希值。奇數(shù)/偶數(shù)反轉(zhuǎn)這種折疊法稱為 邊界折疊法。

4. 平方取中法

平方取中法是先將各個數(shù)據(jù)平方，將平方后數(shù)據(jù)取中間的某段數(shù)字作為索引，例如，對于整數(shù)集 54，26，93，17，77，31，平方取中法如下：

步驟1：先將各個數(shù)據(jù)平方，得到的值如下：

54=2916
26=676
93=8649
17=289
77=5929
31=961

步驟2：取以上平方值的中間數(shù)，即取十位和百位，得到該整數(shù)集中數(shù)據(jù)的哈希地址分別為：

91 67 64 28 92 96

步驟3：若設(shè)置槽位是 11，將步驟 2 得到的數(shù)據(jù)分別除以 11 留余數(shù)，得到的哈希值分別為：

3 1 9 6 4 8

得到的對應(yīng)關(guān)系如下圖所示：

5. 碰撞與溢出問題

哈希算法的理想情況是所有數(shù)據(jù)經(jīng)過哈希函數(shù)運(yùn)算后得到不同的值，但是在實(shí)際情況中即使得到的哈希值不同，也有可能得到相同的地址，這種問題被稱為 碰撞問題。使用哈希算法，將數(shù)據(jù)放到哈希表中存儲數(shù)據(jù)的對應(yīng)位置，若該位置滿了，就會溢出，這種問題被稱為 溢出問題。存在問題就需要解決問題，如何解決碰撞問題與溢出問題很重要。由于常見的解決問題方法有多種，故在后續(xù)博文中進(jìn)行更新。

實(shí)例：用哈希查找算法查找七色光顏色。具體代碼如下：

class HashTable(object):  # 創(chuàng)建哈希表
    def __init__(self):
        self.size = 11  # 哈希表長度
        self.throw = [None] * self.size  # 哈希表數(shù)據(jù)鍵初始化
        self.data = [None] * self.size  # 哈希表數(shù)據(jù)值初始化

    # 假定最終將有一個空槽，除非 key 已經(jīng)存在于  self. throw中。它計(jì)算原始
    # 哈希值，如果該槽不為空，則迭代 rehash 函數(shù)，直到出現(xiàn)空槽。如果非空槽已經(jīng)包含key，
    # 則舊數(shù)據(jù)值將替換為新數(shù)據(jù)值
    def put(self, key, value):  # 輸出鍵值
        hashvalue = self.hashfunction(key, len(self.throw))  # 創(chuàng)建哈希值
        if self.throw[hashvalue] is None:
            self.throw[hashvalue] = key  # 將key值給哈希表的throw
            self.data[hashvalue] = value  # 將value值給哈希表的data
        else:
            if self.throw[hashvalue] == key:
                self.data[hashvalue] = value
            else:
                nextslot = self.rehash(hashvalue, len(self.throw))
                while self.throw[nextslot] is not None and self.throw[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.throw))
                if self.throw[nextslot] is None:
                    self.throw[nextslot] = key
                    self.data[nextslot] = value
                else:
                    self.data[nextslot] = value

    def rehash(self, oldhash, size):
        return (oldhash + 1) % size

    def hashfunction(self, key, size):
        return key % size

    # 從計(jì)算初始哈希值開始。如果值不在初始槽中，則 rehash 用
    # 于定位下一個可能的位置。
    def get(self, key):
        startslot = self.hashfunction(key, len(self.throw))
        data = None
        found = False
        stop = False
        pos = startslot
        while pos is not None and not found and not stop:
            if self.throw[pos] == key:
                found = True
                data = self.data[pos]
            else:
                pos = self.rehash(pos, len(self.throw))
                # 回到了原點(diǎn)，表示找遍了沒有找到
                if pos == startslot:
                    stop = True
        return data

    # 重載載 __getitem__ 和 __setitem__ 方法以允許使用 [] 訪問
    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        return self.put(key, value)


H = HashTable()  # 創(chuàng)建哈希表
H[16] = "紅"  # 給哈希表賦值
H[28] = "橙"
H[32] = "黃"
H[14] = "綠"
H[56] = "青"
H[36] = "藍(lán)"
H[71] = "紫"
print("key的數(shù)據(jù)是：", H.throw)  # 輸出鍵key
print("value的數(shù)據(jù)是：", H.data)  # 輸出值value
print("結(jié)果是:", H[28])  # 根據(jù)key=28查value
print("結(jié)果是:", H[71])  # 根據(jù)key=71查value
print("結(jié)果是:", H[93])  # 根據(jù)key=93查value

程序執(zhí)行結(jié)果如下圖所示：

五、分塊查找算法

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

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

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

步驟2：選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表，即選取上圖所示的各塊的最大值，第一塊最大的值是 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)，此時將第 3 塊內(nèi)的數(shù)據(jù)取出，進(jìn)行順序比較，如下圖所示：

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

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

實(shí)例：實(shí)現(xiàn)分塊查找算法。具體代碼如下：

def search(data, key):  # 用二分查找 想要查找的數(shù)據(jù)在哪塊內(nèi)
    length = len(data)  # 數(shù)據(jù)列表長度
    first = 0  # 第一位數(shù)位置
    last = length - 1  # 最后一個數(shù)據(jù)位置
    print(f"長度:{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是每塊的長度，key是想要查找的數(shù)據(jù)
    length = len(data)  # 表示數(shù)據(jù)列表的長度
    block_length = length // count  # 一共分的幾塊
    if count * block_length != length:  # 每塊長度乘以分塊總數(shù)不等于數(shù)據(jù)總長度
        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:  # 每塊長度要與數(shù)據(jù)長度比較，一旦大于數(shù)據(jù)長度
                break  # 就退出循環(huán)
            block_data.append(data[block_i * count + i])  # 每塊長度要累加上一塊的長度
        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)  # 第二個參數(shù)是塊的長度，最后一個參數(shù)是要查找的元素
print("查找的值得索引位置是:", result)  # 輸出結(jié)果

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

從上面的運(yùn)行結(jié)果看到，當(dāng)查找 150 時，查找結(jié)果完全符合上述描述的步驟。

六、斐波那契查找算法

斐波那契查找也稱為黃金分割法查找，是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割，二分法是取排序好的中間值進(jìn)行分割，而斐波那契查找是根據(jù)黃金分割點(diǎn)進(jìn)行分割。想要掌握斐波那契查找，首先需要了解兩個概念，一個是黃金分割點(diǎn)，另一個是斐波那契數(shù)列。

黃金分割點(diǎn)。黃金分割點(diǎn)是指把一條線段分割為兩部分，使其中一部分與全長之比等于另一部分與這部分之比，其比值取其前三位數(shù)字的近似值是 0.618。0.618 是一個神奇的數(shù)字，在建筑學(xué)和設(shè)計(jì)學(xué)等方面，按照按此比例設(shè)計(jì)的造型就會十分美麗，因此稱為黃金分割。這個分割點(diǎn)就叫作黃金分割點(diǎn)。斐波那契數(shù)列。斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、34、55……，在數(shù)學(xué)上，斐波那契被遞歸方法如下定義：F(1)=1，F(xiàn)(2)=1，F(xiàn)(n) = F(n-1)+F(n-2) (n>=2)。斐波那契數(shù)列越往后，前后兩項(xiàng)的比值越接近 0.618，也就是黃金比例的比值。

斐波那契查找就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的。在斐波那契數(shù)列找一個等于或略大于待查找表長度的數(shù) F(n)，待查找表長度擴(kuò)展為 F(n)-1(如果原來數(shù)組長度不夠 F(n)-1，則需要擴(kuò)展，擴(kuò)展時候用原待查找表最后一項(xiàng)填充)，mid = low + F(n-1) -1，已知 mid 為劃分點(diǎn)，將待查找表劃分為左邊，右邊，即 F(n) 個元素分割為前半部分 F(n-1)-1 個元素，后半部分 F(n-2)-1 個元素，如圖下圖所示：

說明：假如待查找列表長度為 F(n)，不考慮 mid 的情況下，左邊為 F(n - 1)，右邊為 F(n -2)，考慮 mid 的情況下要不左邊是 F(n-1) - 1 或者右邊是 F(n - 2) - 1，邏輯不好寫，如果待查找長度為 F(n) - 1，mid = low + (F(n - 1) - 1) 則不存在這樣的問題。

例如，已經(jīng)有排序好的數(shù)列：9、10、13、15、22、29、37、48、53，要查找的數(shù)據(jù)是 37，如下圖所示：

用斐波那契查找法步驟如下：

說明：斐波那契查找也和二分查找法一樣，需要在查找前，將數(shù)列排序好。

步驟1：先來看一下原始數(shù)據(jù)的長度，如上圖所示長度是 9，再來看斐波那契數(shù)列 1、1、2、3、5、8、13、21、34、55····，從數(shù)據(jù)來看，最接近的數(shù)字是 13，因此將原始數(shù)據(jù)的長度擴(kuò)展到 13，用上圖的最后一個數(shù)據(jù) 53 補(bǔ)齊。如下圖所示：

步驟2：接下來得找查找算法里的中間值了，首先假設(shè)創(chuàng)建斐波那契數(shù)列為 F(n)，斐波那契數(shù)列的規(guī)律 F(n)= F(n-1)+ F(n-2)，上圖已經(jīng)將原數(shù)列長度補(bǔ)充到 13，在斐波那契數(shù)列中 13=8+5，即 F(6)=F(5)+F(4)，則中間是 F(5)，在斐波那契數(shù)列中 F(5)=8，因此 mid=low+F(5)-1=7。如下圖所示：

步驟3：從數(shù)據(jù)上看，mid=7 對應(yīng)的數(shù)據(jù)是 48，目標(biāo)數(shù)據(jù) 37 比 48 小，因此再次尋找以 mid 為分割線的左側(cè)部分?jǐn)?shù)據(jù)，此時 high 的值從 8 的位置變?yōu)?mid-1 的位置，即此時 high=6，low 值不變，依然是 0。如下圖所示：

步驟4：此時圖中所示的數(shù)據(jù)長度變成了 7，再次找此時數(shù)據(jù)的中間值，數(shù)據(jù)長度 7 與斐波那契數(shù)列的數(shù)字 8 比較接近，8=3+5，8 在斐波那契數(shù)列中是 F(5)，即 F(5)=F(4)+F(3)，中間值是 F(4)，在斐波那契數(shù)列中 F(4)=5，此時的 mid=low+F(4)-1=4。如下圖所示：

步驟5：從數(shù)據(jù)上看，mid=4 對應(yīng)的數(shù)據(jù)是 22。目標(biāo)數(shù)據(jù) 37 比 22 大，因此再次尋找以 mid為 分割線的右側(cè)部分?jǐn)?shù)據(jù)，此時 low 的值從 0 的位置變?yōu)?mid+1 的位置，即此時 low=5，high 值不變，依然是 6，如下圖所示：

步驟6：從上圖可知 high=6，最接近的斐波那契數(shù)列的數(shù)據(jù)是 8，8=3+5，8 在斐波那契數(shù)列中是 F(5)，即 F(5)=F(4)+F(3)，虛擬中間值是 F(4)，因?yàn)槭窃谥虚g值的右側(cè)尋找，因此需要計(jì)算 F(n-2)=F(4-2)=F(2)，在斐波那契數(shù)列中 F(2)=2，此時的 mid=low+F(2)-1=5+1=6，如下圖所示：

步驟7：從數(shù)據(jù)上看，mid=4 對應(yīng)的數(shù)據(jù)是 37，目標(biāo)數(shù)據(jù) 37 等于中間值 37，此時返回尋找的位置，即返回 mid 的位置。如果計(jì)算 mid 的值大于 high 的值，就之間返回 high 的值。此時已經(jīng)用斐波那契查找完成尋找目標(biāo)數(shù)據(jù) 37 的任務(wù)。

總結(jié)來說：斐波那契查找與二分查找很相似，它是根據(jù)斐波那契序列的特點(diǎn)對有序表進(jìn)行分割的。它要求開始表中記錄的個數(shù)為某個斐波那契數(shù)小 1，即 k=F(n)-1;開始將 n 值與第 F(n-1) 位置的記錄進(jìn)行比較 (即 mid=low+F(n-1)-1)，比較結(jié)果也分為三種：

相等，mid 位置的元素即為所求。n > F(n-1) 位置的記錄，low=mid+1，n-=2。說明：low=mid+1 說明待查找的元素在 [mid+1,hign]（即右側(cè)）范圍內(nèi)，n-=2 說明范圍 [mid+1,high] 內(nèi)的元素個數(shù)為 k-（F(n-1))= F(n)-1-F(n-1)=F(n)-F(n-1)-1=F(n-2)-1 個，所以可以遞歸的應(yīng)用斐波那契查找。n F(n-1)位置的記錄 ，high=mid-1，n-=1。說明：low=mid+1 說明待查找的元素在 [low,mid-1]（即左側(cè)）范圍內(nèi)，k-=1 說明范圍 [low,mid-1] 內(nèi)的元素個數(shù)為 F(k-1)-1 個，所以可以遞歸的應(yīng)用斐波那契查找。

接下來用Python代碼來實(shí)現(xiàn)以上描述的斐波那契查找。

def fibonacci_search(data, key):
    # 需要一個現(xiàn)成的斐波那契列表。其最大元素的值必須超過查找表中元素個數(shù)的數(shù)值
    F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
         233, 377, 610, 987, 1597, 2584, 4181, 6765]
    low = 0  # 低位
    high = len(data) - 1  # 高位
    # 為了使得查找表滿足斐波那契特性，在表的最后添加幾個同樣的值
    # 這個值是原查找表的最后那個元素的值
    # 添加的個數(shù)由F[k]-1-high決定
    k = 0
    while high > F[k] - 1:
        k += 1
    i = high  # 將i定位到high的位置
    while F[k] - 1 > i:  # 添加數(shù)據(jù)
        data.append(data[high])  # 追加到high之后的位置上
        i += 1
    print("添加后的數(shù)據(jù)", data)  # 輸出追加后的數(shù)據(jù)
    # 算法主邏輯，count用于展示循環(huán)的次數(shù)
    while low = high:  # 滿足低位小于等于高位
        # 為了防止F列表下標(biāo)溢出，設(shè)置if和else
        if k  2:
            mid = low
        else:
            mid = low + F[k - 1] - 1
        print("低位位置：%s, 中間位置：%s,高位位置：%s" % (low, mid, high))  # 輸出每次分割情況
        if key  data[mid]:  # 目標(biāo)數(shù)據(jù)小于中間值數(shù)據(jù)，在左側(cè)尋找
            high = mid - 1  # 高位位置移到mid-1的位置
            k -= 1  # 下標(biāo)k此時減1
        elif key > data[mid]:  # 目標(biāo)數(shù)據(jù)大于中間值數(shù)據(jù)，在右側(cè)尋找
            low = mid + 1  # 低位位置移到mid+1的位置
            k -= 2  # 下標(biāo)k此時減2
        else:  # 否則
            if mid = high:  # 中間值小于等于mid
                return mid  # 此時的結(jié)果是mid就是目標(biāo)值得位置，返回mid即可
            else:  # 如果mid大于了高位位置值
                return high  # 此時的結(jié)果直接返回high的值
    return False


# 驗(yàn)證數(shù)據(jù)
data = [9, 10, 13, 15, 22, 29, 37, 48, 53]  # 數(shù)據(jù)列表
key = int(input("請輸入想要查找的數(shù)據(jù)："))
result = fibonacci_search(data, key)  # 調(diào)用斐波那契查找函數(shù)
print("目標(biāo)數(shù)據(jù)", key, "的位置是", result)  # 輸出結(jié)果

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

從上圖中的運(yùn)行結(jié)果看到，當(dāng)查找 37 時，查找結(jié)果完全符合上述描述的步驟。如果想要進(jìn)行其他數(shù)據(jù)的查找，都可以通過斐波那契查找算法實(shí)現(xiàn)，這里就不一一講解了。

七、六種查找算法的時間復(fù)雜度

在第 1~6 節(jié)中介紹了六種查找算法，本節(jié)就用大 O 表示法來比較一下這四種查找算法的時間復(fù)雜度。先來總結(jié)這四種查找算法的基本思想：

• 順序查找算法：按照數(shù)據(jù)的順序一項(xiàng)一項(xiàng)逐個查找，所以不管數(shù)據(jù)順序如何，都要從頭到尾的遍歷一次。速度比較慢，它的時間復(fù)雜度是 T=O(n)。
• 二分查找算法：將數(shù)據(jù)分割成兩等份，然后用鍵值(要查找的數(shù)據(jù))與中間值比較，逐漸縮短查找范圍。速度比順序查找快，它的時間復(fù)雜度是 T=O(log n)。
• 插補(bǔ)查找算法：按照數(shù)據(jù)的分布，利用公式預(yù)測鍵值所在的位置，快速縮小鍵值所在序列的范圍，慢慢逼近，直到查找到數(shù)據(jù)為止，這種算法比二分查找速度還快，它的時間復(fù)雜度是 T=O(log log(n))。
• 分塊查找算法：要求是順序表，它是順序查找的一種改進(jìn)方法，它的時間復(fù)雜度是 T= O(log2(m)+N/m)。
• 斐波那契查找算法：斐波那契查找就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的。用鍵值(要查找的數(shù)據(jù))與黃金分割點(diǎn)進(jìn)行比較，逐漸縮短查找范圍。它的時間復(fù)雜度是 T=O(log 2n)。
• 哈希查找算法：把一些復(fù)雜的數(shù)據(jù)，通過某種函數(shù)映射(概念和數(shù)學(xué)中映射一樣)關(guān)系，映射成更加易于查找的方式。這種方法速度最快，它的時間復(fù)雜度是 T=O(1)。

六種查找算法的時間復(fù)雜度如下表所示：

到此這篇關(guān)于Python 語言實(shí)現(xiàn)六大查找算法的文章就介紹到這了,更多相關(guān)python查找算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！