Python算法練習(xí)之二分查找算法的實(shí)現(xiàn)

更新時(shí)間：2022年06月16日 08:51:37 作者：小袁ITSuper

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。本文將介紹python如何實(shí)現(xiàn)二分查找算法，幫助大家更好的理解和使用python，感興趣的朋友可以了解下

1. 算法描述

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

回憶之前做過的猜數(shù)字的小游戲，預(yù)先給定一個(gè)小于100的正整數(shù)x，讓你猜猜測過程中給予大小判斷的提示，問你怎樣快速地猜出來?

我們之前做的游戲給定的是10次機(jī)會(huì)，如果我們學(xué)會(huì).二分查找法以后，不管數(shù)字是多少，最多只需要7次就能猜到數(shù)字。

2. 算法分析

1、必須是有序的序列。

2、對(duì)數(shù)據(jù)量大小有要求。

數(shù)據(jù)量太小不適合二分查找，與直接遍歷相比效率提升不明顯。

數(shù)據(jù)量太大也不適合用二分查找，因?yàn)閿?shù)組需要連續(xù)的存儲(chǔ)空間，若數(shù)據(jù)量太大，往往找不到存儲(chǔ)如此大規(guī)模數(shù)據(jù)的連續(xù)內(nèi)存空間。.

3. 算法思路

假設(shè)有一個(gè)有序列表如下:

請(qǐng)問數(shù)字11是否在此列表中，如果在它的索引值為多少?

4. 代碼實(shí)現(xiàn)

純算法實(shí)現(xiàn)

實(shí)現(xiàn)代碼

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

運(yùn)行結(jié)果

遞歸法實(shí)現(xiàn)

在循環(huán)中定義了一個(gè)變量count，如果第一次循環(huán)后count沒有變化，就說明輸入的是有序序列，這時(shí)我們直接return退出循環(huán)，這時(shí)候的時(shí)間復(fù)雜度為O(n)

實(shí)現(xiàn)代碼

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]

def binary_search(seek_number, left, right):
    if left <= right:
        middle = (left + right) // 2
        if seek_number < arr_list[middle]:
            right = middle - 1
        elif seek_number > arr_list[middle]:
            left = middle + 1
        else:
            return middle
        # 進(jìn)行遞歸調(diào)用
        return binary_search(seek_number, left, right)
    # 當(dāng)左側(cè)索引大于右側(cè)索引時(shí)，說明沒有找到
    else:
        return -1

# 查找的數(shù)字
seek_number = 11
# 列表左側(cè)索引
left = 0
# 列表右側(cè)索引
right = len(arr_list) - 1
print("查找的數(shù)字：%s，索引為：%s" % (seek_number, binary_search(seek_number, left, right)))

運(yùn)行結(jié)果