Atcoder　アルゴリズム [二分探索(バイナリサーチ)]編

二分探索とは?

二分探索（バイナリサーチ）は、ソート済みのリストや配列内で特定の値を高速に見つける検索アルゴリズムです。この方法は、探索対象の範囲を半分に絞りながら目的の値を探します。二分探索は、リストが既にソートされている場合に非常に効率的である。N個の要素から特定の数を探す場合、計算量は通常O(N)かかってしまうところ、二分探索の場合O(logN)に抑えられる。

具体例

# 使用例
arr = [1, 2, 4, 5, 7, 8, 9]
target = 5

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



index = binary_search(arr, target)

if index != -1:
    print(f"値 {target} は配列のインデックス {index} に見つかりました。")
else:
    print(f"値 {target} は配列内に見つかりませんでした。")