[Python] 2分探索

2分探索 Binary Search

Pythonで2分探索を実装します。

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

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

ちなみに、Pythonにはbisectという2分探索のためのライブラリがあるので、個人的にBinary Searchを実装して学習してみようという場合以外は、そちらを使うべきと思います。

bisect — 配列二分法アルゴリズム

ループを使った2分探索

def binary_search_loop(data, target):
    imin = 0
    imax = len(data)-1

    while imin <= imax:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return True
        elif target < data[imid]:
            imax = imid -1
        else:
            imin = imid + 1
    return False

再帰を使った2分探索

def binary_search_rec(data, target, imin, imax):
    if imin > imax:
        return False
    else:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return True
        elif target < data[imid]:
            return binary_search_rec(data, target, imin, imid-1)
        else:
            return binary_search_rec(data, target, imid+1, imax)