二分探索

投稿者: | 2022-07-09
0件のコメント
  • 線形探索と比べて処理時間が大幅に短くなる（めちゃくちゃ速い）
  • 事前にソートが必要
  • データが昇順にソートされ並んでいる中から、目的のデータが真ん中より右にあるかを調べる作業を繰り返す。
# 二分探索
def binary_search(data, value):
    left = 0                      # <- 探索する範囲の左端を設定
    right = len(data) - 1　　　　　 # <- 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2  #<- 探索する範囲の中央を計算
        if data[mid] == value:
            return mid
        elif data[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1　　　　　　　　　　　　　# <- 見つからなかった場合
data = [i for i in range(100000000)]
%%timeit
binary_search(data, 85684500)

# 4.93 µs ± 66 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# 線形探索
def linear_search(data, value):
    for i in range(len(data)):
        if data[i] == value:
            return i
    return -1
%%timeit
linear_search(data, 85684500)

# 4.99 s ± 157 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)