Pythonによる二分探索アルゴリズムの詳細な分析

この記事では、python に関する関連知識を提供します。主に、アルゴリズムの説明、アルゴリズム分析、アルゴリズムのアイデアなど、二分探索アルゴリズムに関連する問題を整理しています。以下は、見てみましょう。それはみんなを助けます。

推奨学習: Python ビデオ チュートリアル

1. アルゴリズムの説明

二分法は 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  arr_list[middle]:
        # 左侧索引为中间位置索引+1
        left = middle + 1
    # 如果查找的数字小于中间位置的数字时
    elif seek_number <p>実行結果:</p><p></p><p><img src="https://img.php.cn/upload/article/000/000/067/ab7ca007166584d2196443b3030f239a-4.png" alt="Pythonによる二分探索アルゴリズムの詳細な分析">再帰的メソッドの実装</p><h2></h2>ループ内で変数 count が定義されます。ループ後も変化しないということは、入力が順序付けされたシーケンスであることを意味します。このとき、ループを終了するために直接戻ります。このときの時間計算量は O(n)<blockquote>
<p></p> 実装コードです: </blockquote> <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 中国語 Web サイトの他の関連記事を参照してください。