二分探索 - Algo-List

二分探索アルゴリズム

二分探索(Binary Search)は、ソート済みの配列やリストから目的の値を効率的に探索するアルゴリズムだ。リストが昇順または降順に並んでいることが前提となる。

二分探索の動作原理

対象の配列の中央のインデックスを求める
中央の値が目的の値と一致するかどうかを確認する
中央の値が目的の値より大きい場合は、探索範囲を中央よりも前の部分に絞り込む
中央の値が目的の値より小さい場合は、探索範囲を中央よりも後の部分に絞り込む
探索範囲が空になるまで2~4を繰り返す
探索範囲が空になった場合は、目的の値が存在しないので特別な値(通常は-1)を返す

Pythonによる実装

# binary_search.py
def binary_search(list, target):
  low = 0
  high = len(list) - 1
  while low <= high:
    mid = (low + high) // 2
    if list[mid] == target:
      return mid
    elif list[mid] <; target:
      low = mid + 1
    else:
      high = mid - 1
  return -1

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 5))# 2
print(binary_search(my_list, 6))# -1

探索の早さ

二分探索は、対象のリストがソート済みであることを前提としている。そのため、最悪の場合でも、探索範囲を半分ずつ狭めていくことができる。このため、要素数nに対する時間計算量は O(log n) となる。

一方、線形探索の時間計算量が O(n) であることを考えると、nが大きくなるにつれて二分探索の方がはるかに効率的であることがわかる。例えば、n=1,000,000の場合、二分探索は約20回の比較で目的の値を見つけられるが、線形探索では最悪で1,000,000回の比較が必要になる。

二分探索は、条件さえ整えば非常に高速に動作するアルゴリズムだ。ただし、事前にデータがソート済みであることが前提となるため、ソート処理のコストも考慮する必要がある。