Pythonで二分探索アルゴリズムを適用する方法

二分検索アルゴリズムは、並べ替えられた配列内で特定の要素を探すときに使用できる効率的な検索アルゴリズムです。基本的な考え方は、探索範囲を2つに分けて、中の要素と探す要素の大きさを比較して、探す範囲を縮小し、探す要素が見つかるまでまたは探す要素がないことが確認されるまで繰り返します。

以下の簡潔なサンプルコードは、二分探索アルゴリズムのアプリケーションを表しています：

def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 示例用法
arr = [1, 3, 5, 7, 9, 11, 13]
target = 5
result = binary_search(arr, target)
if result != -1:
print("目标元素在数组中的索引为", result)
else:
print("目标元素不在数组中")

上記の例で、binary_search 関数は、順序付けられた配列 arr と、ターゲット要素 target をパラメータとして受け取り、ターゲット要素の配列内のインデックスを返します。ターゲット要素が配列に存在しない場合は、-1 が返されます。

アルゴリズムでは, まず探索する範囲の左境界left, 右境界rightを定義し, 初期値にはそれぞれ配列の先頭と末尾のインデックスを設定します. 次に, 反復処理に入り, 反復ごとに探索範囲を2つの子範囲に2分し, その中間の要素と探索対象の要素の大小関係によって, 左境界か右境界を更新していきます. 中間の要素が探索対象の要素と同じであれば, 探索対象の要素が見つかったことがわかり, インデックスを返します. 中間の要素が探索対象の要素より小さければ, 右の子範囲に探索対象の要素があるべきなので, 左境界を中間要素の次の位置に更新します. 中間の要素が探索対象の要素より大きければ, 左の子範囲に探索対象の要素があるべきなので, 右境界を中間要素の前の位置に更新します. 左境界が右境界より大きくなれば, 反復処理を抜ける条件になります.

二分探索アルゴリズムは、ソート済みの配列でターゲット要素を高速に検索し、時間計算量がO（log n）です。