二分探索とは
二分探索とは、
です。
二分探索は、「分割統治法」の典型的な例として知られており、各ステップで探索範囲を半分に絞り込んでいきます。
アルゴリズムの概要
二分探索のアルゴリズム
-
-
ステップ1ソート済みの配列の中央の要素を調べる
-
ステップ2探している値が中央の要素と等しければ、探索完了・探している値の方が大きければ左半分を捨てる・探している値の方が小さければ右半分を捨てる
-
ステップ3新たな探索範囲でステップ1,2を繰り返す探索範囲がなくなったら要素は存在しない
-
配列の中から特定の要素を探す問題を例として考えてみましょう。
与えられた配列：[1, 2, 3, 4, 5, 6, 7, 8, 9]
探す数字：6
性能
時間計算量
時間計算量は以下の通りです。
空間計算量
空間計算量は、 \(O(1)\)です。
特徴
長所
短所
用途
実装(Python)
実装
def binary_search(nums, target):
left = 0
right = len(nums)
while left < right:
middle = (left + right) // 2
if nums[middle] == target:
return middle # 見つかった場合、そのインデックスを返す
elif nums[middle] < target:
left = middle + 1
else:
right = middle
return -1 # 見つからなかった場合、-1を返す
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(nums, 5))
print(binary_search(nums, 10))4
-1
モジュールを使用した二分探索の実装
Pythonの標準ライブラリにはbisectモジュールがあり、ソート済みリストに対する二分探索と挿入を効率的に行うことができます。
このbisectモジュールを使用すると、二分探索をより簡潔に実装できます。
import bisect
def binary_search_bisect(nums, target):
index = bisect.bisect_left(nums, target)
if index < len(nums) and nums[index] == target:
return index
return -1
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(nums, 5))
print(binary_search(nums, 10))4
-1
参考文献
コメント