Python詳細解析之二分查找演算法

這篇文章為大家帶來了關於python的相關知識，其中主要整理了二分查找演算法的相關問題，包括了演算法描述、演算法分析、演算法思路等等內容，以下一起來看一下，希望對大家有幫助。

推薦學習：python影片教學

#1.演算法描述

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

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

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

2. 演算法分析

1、必須是有順序的序列。

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

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

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

3. 演算法思路

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


## 請問數字11是否在此清單中，如果在它的索引值為多少?

4.程式碼實作

純演算法實作

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  arr_list[middle]:
        # 左侧索引为中间位置索引+1
        left = middle + 1
    # 如果查找的数字小于中间位置的数字时
    elif seek_number <h2 id="執行結果">執行結果：</h2><blockquote><p></p></blockquote>遞歸法實作<p></p><p>在迴圈中定義了一個變數count，如果第一次循環後count沒有變化，就表示輸入的是有序序列，這時我們直接return退出循環，這時候的時間複雜度為O(n)</p><p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/067/719dc56ca48395be26696a233ba5e483-5.png?x-oss-process=image/resize,p_40" class="lazy" alt="Python詳細解析之二分查找演算法">實現程式碼：</p> <pre class="brush:php;toolbar:false">arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]def binary_search(seek_number, left, right):
    if left  arr_list[middle]:
            left = middle + 1
        else:
            return middle        # 进行递归调用
        return binary_search(seek_number, left, right)
    # 当左侧索引大于右侧索引时，说明没有找到
    else:
        return -1# 查找的数字seek_number = 11# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1print("查找的数字：%s，索引为：%s" % (seek_number, binary_search(seek_number, left, right)))

運行結果：

#######推薦學習：###python影片教學#######

以上是Python詳細解析之二分查找演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！