Python演演算法練習之二分查詢演演算法的實現

2022-06-16 10:02:27

1. 演演算法描述

二分法是一種效率比較高的搜尋方法

回憶之前做過的猜數位的小遊戲，預先給定一個小於100的正整數x，讓你猜猜測過程中給予大小判斷的提示，問你怎樣快速地猜出來?

我們之前做的遊戲給定的是10次機會，如果我們學會.二分查詢法以後，不管數位是多少，最多隻需要7次就能猜到數位。

2. 演演算法分析

1、必須是有序的序列。

2、對資料量大小有要求。

資料量太小不適合二分查詢，與直接遍歷相比效率提升不明顯。

資料量太大也不適合用二分查詢，因為陣列需要連續的儲存空間，若資料量太大，往往找不到儲存如此大規模資料的連續記憶體空間。.

3. 演演算法思路

假設有一個有序列表如下:

請問數位11是否在此列表中，如果在它的索引值為多少?

4. 程式碼實現

純演演算法實現

實現程式碼

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]
# 需要查詢的數位
seek_number = 11
# 儲存一共查詢了幾次
count = 0
# 列表左側索引
left = 0
# 列表右側索引
right = len(arr_list) - 1
# 當左側索引小於等於右側索引時
while left <= right:
    # 取中間的索引位置
    middle = (left + right) // 2
    # 查詢次數進行累加
    count += 1
    # 如果查詢的數位大於中間位置的數位時
    if seek_number > arr_list[middle]:
        # 左側索引為中間位置索引+1
        left = middle + 1
    # 如果查詢的數位小於中間位置的數位時
    elif seek_number < arr_list[middle]:
        # 右側索引為中間位置索引-1
        right = middle - 1
    # 如果等於中間索引資料
    else:
        print('數位：%s找到了，索引值為：%s' % (seek_number, middle))
        break
else:
    print("數位%s 沒有找到" % seek_number)
print("一共用了：%s次查詢" % count)

執行結果

遞迴法實現

在迴圈中定義了一個變數count，如果第一次迴圈後count沒有變化，就說明輸入的是有序序列，這時我們直接return退出迴圈，這時候的時間複雜度為O(n)