Python で アルゴリズム 実装 第2回 二分探索

はじめに

Hello, Terminal！swaponQです！

今回は 第2回 二分探索 です！

二分探索

アルゴリズム

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
個のデータがある場合、時間計算量はである。
個のデータの中央の値を見ることで、1回の操作で個程度（奇数の場合は個、偶数の場合は個または個）の要素を無視することができる。
二分探索 - Wikipedia

実装

binary_search.py

def binary_search(data, value):
    min = 0
    max = len(data) - 1
    while min <= max:
        mid = (min + max) // 2
        if data[mid] == value:
            return mid
        elif data[mid] < value:
            min = mid + 1
        else:
            max = mid - 1
    return -1

if __name__ == '__main__':
    data = [i for i in range(10)]
    print('data =', data)
    value = int(input('input value = '))
    print('index =', binary_search(data, value))

result

data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
input value = 4
index = 4

おわり

今回もお疲れ様でした！
この記事へのコメント・お問い合わせフォームはいつでも大歓迎です。

Goodbye, Terminal… swaponQでした！