[Python] 2分探索

2分探索

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ソート済みのリストにおいて、 目標との中央の値の大小関係により、目標が中央の値の右にあるか、左にあるかを判断することで、目標のある場所を絞り込んでいく検索アルゴリズムです。

時間計算量は $O(log n)$ 、空間計算量は $O(1)$ になります。

 import random

def binary_search(lst, target_val):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] > target_val:
            high = mid - 1
        elif lst[mid] < target_val:
            low = mid + 1
        else:
            return mid
    return False

def print_serach_result(lst, target_val):
    target_index = binary_search(lst, target_val)
    if target_index:
        print(f'{target_val}は{target_index+1}番目に見つかりました。')
    else:
        print(f'{target_val}はリストの中にありません。')


if __name__ == '__main__':
    # 適当なリストの生成
    random.seed(1)
    lst = [random.randint(1, 100) for _ in range(10)]
    lst.sort()
    # [9, 16, 18, 33, 58, 61, 64, 73, 98, 98]
    print(lst) 

    # 線形探索
    # 64は7番目に見つかりました。
    print_serach_result(lst, 64)
    # 63はリストの中にありません。
    print_serach_result(lst, 63)

想定通りの結果を得ることができました。

また、再帰を用いてコードを記述してみます。

import random

def binary_search_recursive(lst, target_val, low=0, high=-1):
    if not lst:
        return False
    if high == -1:
        high = len(lst) -1
    if low == high:
        if lst[low] == target_val:
            return low
        else:
            return False
    mid = low + (high -low) // 2
    if lst[mid] > target_val:
        return binary_search_recursive(lst, target_val, low, mid-1)
    elif lst[mid] < target_val:
        return binary_search_recursive(lst, target_val, mid+1, high)
    else:
        return mid

def print_serach_result(lst, target_val):
    target_index = binary_search_recursive(lst, target_val)
    if target_index:
        print(f'{target_val}は{target_index+1}番目に見つかりました。')
    else:
        print(f'{target_val}はリストの中にありません。')


if __name__ == '__main__':
    # 適当なリストの生成
    random.seed(1)
    lst = [random.randint(1, 100) for _ in range(10)]
    lst.sort()
    # [9, 16, 18, 33, 58, 61, 64, 73, 98, 98]
    print(lst) 

    # 線形探索
    # 64は7番目に見つかりました。
    print_serach_result(lst, 64)
    # 63はリストの中にありません。
    print_serach_result(lst, 63)

こちらも想定通りの結果を得ることができました。