線形探索によるアプローチ
最初に、最も単純な解法である線形探索（総当たり）について検討します。この手法では、配列の先頭から順に各要素を確認し、目的の値と一致するインデックスを返します。
def linear_search(data_array, search_val):
for i in range(len(data_array)):
if data_array[i] == search_val:
return i
return -1
このアプローチは直感的ですが、計算量は O(n) であり、データ量が増加するとパフォーマンスが低下します。
二分探索アルゴリズムの適用
二分探索を適用するには、配列がソートされており、重複する要素が含まれていないことが前提条件となります。これらの条件が満たされる場合、探索範囲を毎回半分に絞り込む二分探索が非常に効率的です。
二分探索の実装における最大の難点は境界条件の処理です。ループ条件やポインタの更新方法（`left < right` か `left <= right` か、`right = middle` か `right = middle - 1` か）は、どのように区間を定義するかによって決まります。この区間の定義を「不変量」として守り続けることが、バグのない実装への鍵となります。
一般的に、区間の定義は以下の2パターンのいずれかを使用します。
- 左閉右閉区間:
[left, right] - 左閉右開区間:
[left, right)
パターン1：左閉右閉区間 [left, right] を使用する場合
この定義では、探索対象の区間に左右両端の値を含めます。これに基づき、ループと更新処理を以下のように記述します。
def binary_search_closed(arr, target):
low, high = 0, len(arr) - 1
# low == high の場合も有効な区間のため、<= を使用
while low <= high:
center = low + (high - low) // 2
if arr[center] > target:
# center の位置はtargetではないため、次の区間は [low, center - 1]
high = center - 1
elif arr[center] < target:
# center の位置はtargetではないため、次の区間は [center + 1, high]
low = center + 1
else:
return center # 目的の値を見つけた
return -1 # 見つからなかった場合
ポイントは、arr[center] が目的の値でないことが確定した際、そのインデックス自体を次回の探索範囲から確実に除外するために -1 または +1 を行う点です。
パターン2：左閉右開区間 [left, right) を使用する場合
次に、右端を区間に含めない定義で考えます。これにより、ループ条件と更新ロジックが変わります。
def binary_search_half_open(arr, target):
low, high = 0, len(arr)
# [low, high) において low == high は空の区間を意味するため、< を使用
while low < high:
center = low + (high - low) // 2
if arr[center] > target:
# center の位置はtargetではないため、次の区間は [low, center)
# 右側は開区間なので center 自体を指定すれば除外される
high = center
elif arr[center] < target:
# 次の区間は [center + 1, high)
low = center + 1
else:
return center # 目的の値を見つけた
return -1 # 見つからなかった場合
こちらのパターンでは、右側の境界値が探索範囲に含まれないため、high を更新する際に center をそのまま代入します。
計算量と実装の補足
二分探索は探索範囲を反復ごとに半減させるため、時間計算量は O(log n) となります。空間計算量は、変数を数個しか使用しないため O(1) です。
なお、実装の際にはPythonの除算演算子の違いに注意が必要です。/ は浮動小数点数を返しますが、// は切り捨てられた整数を返します。インデックス操作を行う場合は、必ず整数除算 // を使用してください。
# 整数除算の例
print(10 // 3) # 出力: 3
print(10 / 3) # 出力: 3.3333...