Pythonによる二分探索アルゴリズムの詳細な分析-Python チュートリアル-php.cn

この記事では、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 実行結果:
再帰的メソッドの実装
ループ内で変数 count が定義されます。ループ後も変化しないということは、入力が順序付けされたシーケンスであることを意味します。このとき、ループを終了するために直接戻ります。このときの時間計算量は O(n) 
 実装コードです: 
 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)))
        
         ログイン後にコピー