Pythonでバイナリサーチ(二分探索)

Qiita初投稿です。

今回は、バイナリサーチをループと再帰の2パターンで実装してみました。

##ループでバイナリサーチ

binary_search_loop.py

from typing import List


def binary_search_loop(data: List[int], target: int) -> int:
    left, right = 0, len(data)

    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return None


if __name__ == "__main__":
    data: List[int] = [int(x) for x in input("ソート済配列(スペース区切り)を入力: ").split()] # 内包表記を使った
    target = int(input("targetを入力: "))

    result = binary_search_loop(data, target)
    if result is not None:
        print(f"found: {result}番目にありました")
    else:
        print("not found")

##再帰でバイナリサーチ

binary_search_recursion.py

from typing import List


def binary_search_recursion(data: List[int], target: int) -> int:
    def recursion(left=0, right=len(data) - 1):
        if left > right:
            return None

        mid = (left + right) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            return recursion(mid + 1, right)
        else:
            return recursion(left, mid - 1)

    return recursion()


if __name__ == "__main__":
    data: List[int] = list(map(int, input("ソート済配列(スペース区切り)を入力: ").split())) # mapを使った
    target = int(input("targetを入力: "))

    result = binary_search_recursion(data, target)
    if result is not None:
        print(f"found: {result}番目にありました")
    else:
        print("not found")

##気付いたことなど

• input()で得られるデータはstr型なのでint型に変換する。
  • str型のままだと比較のところで数字じゃなく文字コードで比較されてしまう。