詳解Python查找算法的實(shí)現(xiàn)(線性,二分,分塊,插值)

更新時(shí)間：2022年04月24日 15:43:09 作者：一枚大果殼

這篇文章主要為大家介紹了Python中常見的四種查找算法的實(shí)現(xiàn)：線性、二分、分塊和插值，文中通過圖片詳細(xì)講解了它們實(shí)現(xiàn)的原理與代碼，需要的可以參考一下

線性查找：線性查找也稱為順序查找，用于在無序數(shù)列中查找。
二分查找：二分查找也稱為折半查找，其算法用于有序數(shù)列。
插值查找：插值查找是對二分查找算法的改進(jìn)。
分塊查找：又稱為索引順序查找，它是線性查找的改進(jìn)版本。
樹表查找：樹表查找又可分二叉查找樹、平衡二叉樹查找。
哈希查找：哈希查找可以直接通過關(guān)鍵字查找到所需要數(shù)據(jù)。

因樹表查找、哈希查找的所需篇幅較多，就不在本文講解。本文將詳細(xì)介紹除樹表、哈希之外的查找算法，并分析每一種算法的優(yōu)點(diǎn)和缺點(diǎn)，并提出相應(yīng)的優(yōu)化方案。

1. 線性查找

線性查找也稱為順序查找，線性查找屬于原始、窮舉、暴力查找算法。容易理解、編碼實(shí)現(xiàn)也簡單。但是在數(shù)據(jù)量較多時(shí)，因其算法思想是樸素、窮舉的，算法中沒有太多優(yōu)化設(shè)計(jì)，性能會很低下。

線性查找思想：

從頭至尾逐一掃描原始列表中的每一個(gè)數(shù)據(jù)，并和給定的關(guān)鍵字進(jìn)行比較。
如果比較相等，則查找成功。
當(dāng)掃描結(jié)束后，仍然沒有找到與給定關(guān)鍵字相等的數(shù)據(jù)，則宣布查找失敗。

根據(jù)線性查找算法的描述，很容易編碼實(shí)現(xiàn)：

'''
線性查找算法
參數(shù)：
    nums: 序列
    key:關(guān)鍵字
返回值：
    關(guān)鍵字在序列中的位置
    如果沒有，則返回 -1
'''
def line_find(nums, key):
    for i in range(len(nums)):
        if nums[i] == key:
            return i
    return -1
'''
測試線性算法
'''
if __name__ == "__main__":
    nums = [4, 1, 8, 10, 3, 5]
    key = int(input("請輸入要查找的關(guān)鍵字："))
    pos = line_find(nums, key)
    print("關(guān)鍵字 {0} 在數(shù)列的第 {1} 位置".format(key, pos))
'''
輸出結(jié)果：
請輸入要查找的關(guān)鍵字：3
關(guān)鍵字 3 在數(shù)列的 4 位置
'''

線性查找算法的平均時(shí)間復(fù)雜度分析。

1.運(yùn)氣最好的情況：如果要查找的關(guān)鍵字恰好在數(shù)列的第 1 個(gè)位置，則只需要查找 1 次就可以了。

如在數(shù)列=[4,1,8,10,3,5]中查找關(guān)鍵字 4 。

只需要查找 1 次。

2.運(yùn)氣最不好的情況：一至掃描到數(shù)列最尾部時(shí)，才找到關(guān)鍵字。

如在數(shù)列=[4,1,8,10,3,5]中查找是否存在關(guān)鍵字 5 。

則需要查找的次數(shù)等于數(shù)列的長度，此處即為 6 次。

3.運(yùn)氣不好不壞：如果要查找的關(guān)鍵字在數(shù)列的中間某個(gè)位置，則查找的概率是 1/n 。

n 為數(shù)列長度。

線性查找的平均查找次數(shù)應(yīng)該=(1+n)/2。換成大 O 表示法則為 O(n) 。

大 O 表示法中忽視常量。

線性查找最糟糕情況是：掃描完整個(gè)數(shù)列后，沒有所要查找的關(guān)鍵字。

如在數(shù)列=[4,1,8,10,3,5]中查找是否存在關(guān)鍵字 12 。

掃描了 6 次后，鎩羽而歸！！

改良線性查找算法

可以對線性查找算法進(jìn)行相應(yīng)的優(yōu)化。如設(shè)置“前哨站”。所謂“前哨站”，就是把要查找的關(guān)鍵字在查找之前插入到數(shù)列的尾部。

def line_find_(nums, key):
    i = 0
    while nums[i] != key:
        i += 1
    return -1 if i == len(nums)-1 else i

'''
測試線性算法
'''
if __name__ == "__main__":
    nums = [4, 1, 8, 10, 3, 5]
    key = int(input("請輸入要查找的關(guān)鍵字："))
    # 查找之前，先把關(guān)鍵字存儲到列到的尾部
    nums.append(key)
    pos = line_find_(nums, key)
    print("關(guān)鍵字 {0} 在數(shù)列的第 {1} 位置".format(key, pos))

用"前哨站"優(yōu)化后的線性查找算法的時(shí)間復(fù)雜度沒有變化，O(n)。或者說從 2 者代碼上看，也沒有太多變化。

但從代碼的實(shí)際運(yùn)行角度而言，第 2 種方案減少了 if 指令的次數(shù)，同樣減少了編譯后的指令，也就減少了 CPU執(zhí)行指令的次數(shù)，這種優(yōu)化屬于微優(yōu)化，不是算法本質(zhì)上的優(yōu)化。

使用計(jì)算機(jī)編程語言所編寫的代碼為偽指令代碼。

經(jīng)過編譯后的指令代碼叫 CPU 指令集。

有一種優(yōu)化方案就是減少編譯后的指令集。

2. 二分查找

二分查找屬于有序查找，所謂有序查找，指被查找的數(shù)列必須是有序的。如在數(shù)列=[4,1,8,10,3,5,12]中查找是否存在關(guān)鍵字 4 ，因數(shù)列不是有序的，所以不能使用二分查找，如果要使用二分查找算法，則需要先對數(shù)列進(jìn)行排序。

二分查找使用了二分（折半）算法思想，二分查找算法中有 2 個(gè)關(guān)鍵信息需要隨時(shí)獲?。?/p>

一個(gè)是數(shù)列的中間位置 mid_pos。
一個(gè)是數(shù)列的中間值mid_val。

現(xiàn)在通過在數(shù)列 nums=[1,3,4,5,8,10,12] 中查找關(guān)鍵字 8來了解二分查找的算法流程。

在進(jìn)行二分查找之前，先定義 2 個(gè)位置（指針）變量：

左指針 l_idx 初始指向數(shù)列的最左邊數(shù)字。
右指針 r_idx 初始指向數(shù)列的最右邊數(shù)字。

第 1 步：通過左、右指針的當(dāng)前位置計(jì)算出數(shù)列的中間位置 mid_pos=3，并根據(jù) mid_pos 的值找出數(shù)列中間位置所對應(yīng)的值 mid_val=nums[mid_pos] 是 5。

二分查找算法的核心就是要找出數(shù)列中間位置的值。

第 2 步：把數(shù)列中間位置的值和給定的關(guān)鍵字相比較。這里關(guān)鍵字是 8，中間位置的值是 5，顯然 8 是大于 5，因?yàn)閿?shù)列是有序的，自然會想到?jīng)]有必要再與數(shù)列中 5 之前的數(shù)字比較，而是專心和 5 之后的數(shù)字比較。

一次比較后再次查找的數(shù)列范圍縮小了一半。這也是二分算法的由來。

第 3 步：根據(jù)比較結(jié)果，調(diào)整數(shù)列的大小，這里的大小調(diào)整不是物理結(jié)構(gòu)上調(diào)整，而是邏輯上調(diào)整，調(diào)整后原數(shù)列沒有變化。也就是通過修改左指針或右指針的位置，從邏輯上改變數(shù)列大小。調(diào)整后的數(shù)列如下圖。

二分查找算法中數(shù)列的范圍由左指針到右指針的長度決定。

第 4 步：重復(fù)上述步驟，至到找到或找不到為止。

編碼實(shí)現(xiàn)二分查找算法

'''
二分查找算法
'''
def binary_find(nums, key):
    # 初始左指針
    l_idx = 0
    # 初始在指針
    r_ldx = len(nums) - 1
    while l_idx <= r_ldx:
        # 計(jì)算出中間位置
        mid_pos = (r_ldx + l_idx) // 2
        # 計(jì)算中間位置的值
        mid_val = nums[mid_pos]
        # 與關(guān)鍵字比較
        if mid_val == key:
            # 出口一：比較相等，有此關(guān)鍵字，返回關(guān)鍵字所在位置
            return mid_pos
        elif mid_val > key:
            # 說明查找范圍應(yīng)該縮少在原數(shù)的左邊
            r_ldx = mid_pos - 1
        else:
            l_idx = mid_pos + 1
    # 出口二：沒有查找到給定關(guān)鍵字
    return -1

'''
測試二分查找
'''
if __name__ == "__main__":
    nums = [1, 3, 4, 5, 8, 10, 12]
    key = 3
    pos = binary_find(nums, key)
    print(pos)

通過前面對二分算法流程的分析，可知二分查找的子問題和原始問題是同一個(gè)邏輯，所以可以使用遞歸實(shí)現(xiàn)：

'''
遞歸實(shí)現(xiàn)二分查找
'''
def binary_find_dg(nums, key, l_idx, r_ldx):
    if l_idx > r_ldx:
        # 出口一：沒有查找到給定關(guān)鍵字
        return -1
    # 計(jì)算出中間位置
    mid_pos = (r_ldx + l_idx) // 2
    # 計(jì)算中間位置的值
    mid_val = nums[mid_pos]
    # 與關(guān)鍵字比較
    if mid_val == key:
        # 出口二：比較相等，有此關(guān)鍵字，返回關(guān)鍵字所在位置
        return mid_pos
    elif mid_val > key:
        # 說明查找范圍應(yīng)該縮少在原數(shù)的左邊
        r_ldx = mid_pos - 1
    else:
        l_idx = mid_pos + 1
    return binary_find_dg(nums, key, l_idx, r_ldx)
'''
測試二分查找
'''
if __name__ == "__main__":
    nums = [1, 3, 4, 5, 8, 10, 12]
    key = 8
    pos = binary_find_dg(nums, key,0,len(nums)-1)
    print(pos)

二分查找性能分析：

二分查找的過程用樹形結(jié)構(gòu)描述會更直觀，當(dāng)搜索完畢后，繪制出來樹結(jié)構(gòu)是一棵二叉樹。

1.如上述代碼執(zhí)行過程中，先找到數(shù)列中的中間數(shù)字 5，然后以 5 為根節(jié)點(diǎn)構(gòu)建唯一結(jié)點(diǎn)樹。

2.5 和關(guān)鍵字 8 比較后，再在以數(shù)字 5 為分界線的右邊數(shù)列中找到中間數(shù)字10，樹形結(jié)構(gòu)會變成下圖所示。

3.10 和關(guān)鍵字 8比較后，再在10 的左邊查找。

查找到8 后，意味著二分查找已經(jīng)找到結(jié)果，只需要 3 次就能查找到最終結(jié)果。

從二叉樹的結(jié)構(gòu)上可以直觀得到結(jié)論：二分查找關(guān)鍵字的次數(shù)由關(guān)鍵字在二叉樹結(jié)構(gòu)中的深度決定。

4.上述是查找給定的數(shù)字8，為了能查找到數(shù)列中的任意一個(gè)數(shù)字，最終完整的樹結(jié)構(gòu)應(yīng)該如下圖所示。

很明顯，樹結(jié)構(gòu)是標(biāo)準(zhǔn)的二叉樹。從樹結(jié)構(gòu)上可以看出，無論查找任何數(shù)字，最小是 1 次，如查找數(shù)字 5，最多也只需要 3 次，比線性查找要快很多。

根據(jù)二叉樹的特性，結(jié)點(diǎn)個(gè)數(shù)為 n 的樹的深度為 h=log2(n+1)，所以二分查找算法的大 O 表示的時(shí)間復(fù)雜度為 O(logn)，是對數(shù)級別的時(shí)間度。

當(dāng)對長度為1000的數(shù)列進(jìn)行二分查找時(shí)，所需次數(shù)最多只要 10 次，二分查找算法的效率顯然是高效的。

但是，二分查找需要對數(shù)列提前排序，前面的時(shí)間復(fù)雜度是沒有考慮排序時(shí)間的。所以，二分查找一般適合數(shù)字變化穩(wěn)定的有序數(shù)列。

3. 插值查找

插值查找本質(zhì)是二分查找，插值查找對二分查找算法中查找中間位置的計(jì)算邏輯進(jìn)行了改進(jìn)。

原生二分查找算法中計(jì)算中間位置的邏輯：中間位置等于左指針位置加上右指針位置然后除以 2。

    # 計(jì)算中間位置
    mid_pos = (r_ldx + l_idx) // 2

插值算法計(jì)算中間位置邏輯如下所示：

key 為要查找的關(guān)鍵字?。?/p>

# 插值算法中計(jì)算中間位置
mid_pos = l_idx + (key - nums[l_idx]) // (nums[r_idx] - nums[l_idx]) * (r_idx - l_idx)

編碼實(shí)現(xiàn)插值查找：

# 插值查找基于二分法，只是mid計(jì)算方法不同
def binary_search(nums, key):
    l_idx = 0
    r_idx = len(nums) - 1
    old_mid = -1
    mid_pos = None
    while l_idx < r_idx and nums[0] <= key and nums[r_idx] >= key and old_mid != mid_pos:
        # 中間位置計(jì)算
        mid_pos = l_idx + (key - nums[l_idx]) // (nums[r_idx] - nums[l_idx]) * (r_idx - l_idx)
        old_mid = mid_pos
        if nums[mid_pos] == key:
            return "index is {}, target value is {}".format(mid_pos, nums[mid_pos])
            # 此時(shí)目標(biāo)值在中間值右邊，更新左邊界位置
        elif nums[mid_pos] < key:
            l_idx = mid_pos + 1
        # 此時(shí)目標(biāo)值在中間值左邊，更新右邊界位置
        elif nums[mid_pos] > key:
            r_idx = mid_pos - 1
    return "Not find"

li =[1, 3, 4, 5, 8, 10, 12]
print(binary_search(li, 6))

插值算法的中間位置計(jì)算時(shí)，對中間位置的計(jì)算有可能多次計(jì)算的結(jié)果是一樣的，此時(shí)可以認(rèn)為查找失敗。

插值算法的性能介于線性查找和二分查找之間。

當(dāng)數(shù)列中數(shù)字較多且分布又比較均勻時(shí)，插值查找算法的平均性能比折半查找要好的多。如果數(shù)列中數(shù)據(jù)分布非常不均勻，此種情況下插值算法并不是最好的選擇。

4. 分塊查找

分塊查找類似于數(shù)據(jù)庫中的索引查詢，所以分塊查找也稱為索引查找。其算法的核心還是線性查找。

現(xiàn)有原始數(shù)列 nums=[5,1,9,11,23,16,12,18,24,32,29,25]，需要查找關(guān)鍵字11 是否存在。

第 1 步：使用分塊查找之前，先要對原始數(shù)列按區(qū)域分成多個(gè)塊。至于分成多少塊，可根據(jù)實(shí)際情況自行定義。分塊時(shí)有一個(gè)要求，前一個(gè)塊中的最大值必須小于后一個(gè)塊的最小值。

塊內(nèi)部無序，但要保持整個(gè)數(shù)列按塊有序。

分塊查找要求原始數(shù)列從整體上具有升序或降序趨勢，如果數(shù)列的分布不具有趨向性，如果仍然想使用分塊查找，則需要進(jìn)行分塊有序調(diào)整。

第 2 步：根據(jù)分塊信息，建立索引表。索引表至少應(yīng)該有 2 個(gè)字段，每一塊中的最大值數(shù)字以及每一塊的起始地址。顯然索引表中的數(shù)字是有序的。

第 3 步：查找給定關(guān)鍵字時(shí)，先查找索引表，查詢關(guān)鍵字應(yīng)該在那個(gè)塊中。如查詢關(guān)鍵字 29，可知應(yīng)該在第三塊中，然后根據(jù)索引表中所提供的第三塊的地址信息，再進(jìn)入第三塊數(shù)列，按線性匹配算法查找29 具體位置。

編碼實(shí)現(xiàn)分塊查找：

先編碼實(shí)現(xiàn)根據(jù)分塊數(shù)量、創(chuàng)建索引表，這里使用二維列表保存儲索引表中的信息。

'''
分塊：建立索引表
參數(shù)：
    nums 原始數(shù)列
    blocks 塊大小
'''
def create_index_table(nums, blocks):
    # 索引表使用列表保存
    index_table = []
    # 每一塊的數(shù)量
    n = len(nums) // blocks
    for i in range(0, len(nums), n):
        # 索引表中的每一行記錄
        tmp_lst = []
        # 最大值
        tmp_lst.append(max(nums[i:i + n-1]))
        # 起始地址
        tmp_lst.append(i)
        # 終止地址
        tmp_lst.append(i + n - 1)
        # 添加到索引表中
        index_table.append(tmp_lst)
    return index_table
'''
測試分塊
'''
nums = [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25]
it = create_index_table(nums, 3)
print(it)
'''
輸出結(jié)果：
[[11, 0, 3], [23, 4, 7], [32, 8, 11]]
'''

代碼執(zhí)行后，輸出結(jié)果和分析的結(jié)果一樣。

以上代碼僅對整體趨勢有序的數(shù)列進(jìn)行分塊。如果整體不是趨向有序，則需要提供相應(yīng)塊排序方案，有興趣者自行完成。

如上代碼僅為說明分塊查找算法。

分塊查找的完整代碼：

'''
分塊：建立索引表
參數(shù)：
    nums 原始數(shù)列
    blocks 塊大小
'''
def create_index_table(nums, blocks):
    # 索引表使用列表保存
    index_table = []
    # 每一塊的數(shù)量
    n = len(nums) // blocks
    for i in range(0, len(nums), n):
        tmp_lst = []
        tmp_lst.append(max(nums[i:i + n - 1]))
        tmp_lst.append(i)
        tmp_lst.append(i + n - 1)
        index_table.append(tmp_lst)
    return index_table

'''
使用線性查找算法在對應(yīng)的塊中查找
'''
def lind_find(nums, start, end):
    for i in range(start, end):
        if key == nums[i]:
            return i
            break
    return -1

'''
測試分塊
'''
nums = [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25]
key = 16
# 索引表
it = create_index_table(nums, 3)
# 索引表的記錄編號
pos = -1
# 在索引表中查詢
for n in range(len(it) - 1):
    # 是不是在第一塊中
    if key <= it[0][0]:
        pos = 0
    # 其它塊中
    if it[n][0] < key <= it[n + 1][0]:
        pos = n + 1
        break
if pos == -1:
    print("{0} 在 {1} 數(shù)列中不存在".format(key, nums))
else:
    idx = lind_find(nums, it[pos][1], it[pos][2] + 1)
    if idx != -1:
        print("{0} 在 {1} 數(shù)列的 {2} 位置".format(key, nums, idx))
    else:
        print("{0} 在 {1} 數(shù)列中不存在".format(key, nums))
'''
輸出結(jié)果
16 在 [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25] 數(shù)列的第 5 位置
'''

分塊查找對于整體趨向有序的數(shù)列，其查找性能較好。但如果原始數(shù)列整體不是有序，則需要提供塊排序算法，時(shí)間復(fù)雜度沒有二分查找算法好。

分塊查找需要建立索引表，這也需要額外的存儲空間，其空間復(fù)雜度較高。其優(yōu)于二分的地方在于只需要對原始數(shù)列進(jìn)行部分排序。本質(zhì)還是以線性查找為主。