Ptyhonで実装するシンプルな二分探索
二分探索とは、配列やリストの中から、特定の値を効率的に探すアルゴリズムのことを指します。このアルゴリズムでは、配列やリストを半分に分割し、探したい値と比較します。比較した結果、探したい値が、分割された配列やリストのどちらにあるかを判断し、さらにその部分を分割して探索を続けます。これを繰り返すことで、最終的に探したい値が見つかるか、配列やリストを完全に探索したことを示すNoneが返されます。
以下に、Pythonで二分探索を行うプログラムを記載します。このプログラムでは、整数値の配列[1, 2, 3, 4, 5, 6, 7]から、値が4のを探します。
def binary_search(numbers, value):
# 探索する範囲の左端点のインデックス
left = 0
# 探索する範囲の右端点のインデックス
right = len(numbers) - 1
while left <= right:
# 探索する範囲の中央のインデックスを計算する
mid = (left + right) // 2
# 探索する値が、中央のインデックスの値より小さい場合
if value < numbers[mid]:
# 探索する範囲を、中央のインデックスより左側に絞り込む
right = mid - 1
# 探索する値が、中央のインデックスの値より大きい場合
elif value > numbers[mid]:
# 探索する範囲を、中央のインデックスより右側に絞り込む
left = mid + 1
# 探索する値が、中央のインデックスの値と等しい場合
else:
# 探索した値を返す
return numbers[mid]
# 探索する値が見つからなかった場合は、Noneを返す
return None
# 整数値の配列を定義する
numbers = [1, 2, 3, 4, 5, 6, 7]
# 配列から値が4の要素を探す
result = binary_search(numbers, 4)
# 探した結果を出力する
print(result) # => 4
二分探索の実行速度は、O(log n)です。これは、配列やリストを半分に分割することで、探索する値を効率的に見つけることができるためです。
たとえば、要素数が1,000の場合、二分探索では10回の比較で値を探すことができます。一方、線形探索では、全ての要素を比較する必要があるため、最短で1回、最悪で1,000回の比較が必要になります。
再帰版
def binary_search(numbers, value, left, right):
# 再帰の終了条件
# 探索する範囲が存在しない場合
if left > right:
return None
# 探索する範囲の中央のインデックスを計算する
mid = (left + right) // 2
# 探索する値が、中央のインデックスの値より小さい場合
if value < numbers[mid]:
# 探索する範囲を、中央のインデックスより左側に絞り込む
return binary_search(numbers, value, left, mid - 1)
# 探索する値が、中央のインデックスの値より大きい場合
elif value > numbers[mid]:
# 探索する範囲を、中央のインデックスより右側に絞り込む
return binary_search(numbers, value, mid + 1, right)
# 探索する値が、中央のインデックスの値と等しい場合
else:
# 探索した値を返す
return numbers[mid]
# 整数値の配列を定義する
numbers = [1, 2, 3, 4, 5, 6, 7]
# 配列から値が4の要素を探す
result = binary_search(numbers, 4, 0, len(numbers) - 1)
# 探した結果を出力する
print(result) # => 4
どちらも名著です。是非ゲットしてみてください。