二分探索法とは、ソートされた配列に対して、目的の要素を探すアルゴリズムのことです。このアルゴリズムは、線形探索法に比べて計算量が少なく、大量のデータを高速に検索することができます。Pythonには、二分探索法を実装するための様々な方法がありますが、ここでは最も基本的な方法を紹介します。
二分探索法のアルゴリズム
二分探索法は、ソートされたリストや配列から目的の要素を効率的に探すアルゴリズムです。配列の中央の要素を取り出し、目的の要素がその要素よりも小さいか大きいかを比較します。目的の要素が中央の要素より小さい場合は、配列の左側を探索し、大きい場合は配列の右側を探索します。このようにして、配列を半分に削ることで、探索範囲を劇的に狭めることができます。このプロセスを繰り返すことで、目的の要素を効率的に見つけることができます。二分探索法は、O(log n)の計算量で実行できるため、非常に高速です。
具体的には下記の手順で実装します。
- ソートされた配列を準備します。
- 配列の中央の要素を選択します。
- 中央の要素と目的の要素を比較します。
- 目的の要素が中央の要素より小さい場合、配列の左側を探索します。
- 目的の要素が中央の要素より大きい場合、配列の右側を探索します。
- 目的の要素が中央の要素と等しい場合、目的の要素が見つかったことになります。
- 目的の要素が見つかるまで、2〜6のステップを繰り返します。
具体例とコード
次の例では、二分探索法を使用して、配列の中から目的の数値を探します。この例では、配列に 1, 3, 5, 7, 9 の数字があり、目的の数字は 5 です。
def binary_search(arr, target): low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return None arr = [1, 3, 5, 7, 9] target = 5 result = binary_search(arr, target) if result is not None: print(f"目的の数字 {target} は、配列のインデックス {result} にあります。") else: print(f"目的の数字 {target} は、配列に見つかりませんでした。")
この例では、binary_searchという関数を定義しています。この関数は、arrとtargetという2つの引数を受け取ります。arrは、ソートされた配列で、targetは検索する数値です。関数は、whileループを使用して、配列の中央要素を選択します。中央の要素が目的の要素と一致する場合は、そのインデックスを返します。それ以外の場合は、目的の要素が中央の要素より小さい場合は、配列の左側を探索し、大きい場合は配列の右側を探索します。そして、目的の要素が見つかるまでこのプロセスを繰り返します。もし目的の要素が見つからなければ、Noneを返します。
例では、arrに[1, 3, 5, 7, 9]があり、targetに 5が設定されています。binary_search関数を呼び出して、目的の数字を探します。目的の数字が見つかった場合は、目的の数字とそのインデックスが表示されます。目的の数字が見つからなかった場合は、配列に見つからなかったことを示すメッセージが表示されます。この例は、非常に基本的な二分探索法の実装であり、より高度なアルゴリズムが存在します。しかし、Pythonで二分探索法を実装するには、この基本的なアルゴリズムを理解することが重要です。
まとめ
Pythonでの二分探索法は、ソートされた配列を高速に検索するための非常に効率的なアルゴリズムです。この記事では、基本的な二分探索法のアルゴリズムを説明し、具体例と共にPythonのコードを紹介しました。Pythonの二分探索法を理解することで、より高度なアルゴリズムを実装するための基礎を築くことができます。
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 [ 米田優峻 ]
二分探索法以外の探索アルゴリズムについては、下記の記事で解説しています。
