Python

Pythonで学ぶアルゴリズム 二分探索

  /

二分探索を実装してみます。

概要

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

二分探索 – Wikipedia

サンプルコード

import random


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


data = sorted(random.sample(range(1, 42), 10))
i = data[random.randint(1, 9)]
print("data : ", data)
print("target : ", i)
print("result : ", binary_search(data, i))

実行結果（例）

data :  [3, 4, 6, 8, 9, 11, 14, 21, 26, 38]
target :  11
result :  5
RELATED POST