【bisect】Pythonで二分探索する方法を解説

本記事ではPythonで二分探索する方法を解説します。具体的にはPythonの標準モジュールであり、二分探索の機能を提供するbisectの使い方を説明します。

二分探索とは

二分探索とは、ソート済みの配列やリストから特定の値を効率的に探すアルゴリズムです。探索対象のデータを半分に分割しながら検索を進めるため、線形探索（リストを1つずつ調べる方法）よりも高速です。

二分探索の特徴

• 事前にデータがソートされている必要がある
• 時間計算量は O(log N)（データ数Nに対して対数的な時間で探索できる）
• リストの中央を基準に検索を繰り返す

bisectの使い方

bisectモジュールはソート済みのリストに対して効率的に要素の挿入位置を見つけたり、挿入したりするための関数を提供します。内部的には二分探索を使用しているため、線形探索よりも高速に処理が可能です。

bisectモジュールには、主に以下の4つの関数が含まれています。

bisect_left と bisect_right

• 引数:
  • a: ソート済みのリスト
  • x: 挿入したい値
  • lo: 検索範囲の開始インデックス（デフォルトは0）
  • hi: 検索範囲の終了インデックス（デフォルトはNone, リストの終端まで）
  • key: (Python 3.10 以降) 各要素を比較するための関数（デフォルトはNone）
• 動作:
  • bisect_left(a, x): x を挿入できる最も左側（最小のインデックス）の位置を返します。
  • bisect_right(a, x): x を挿入できる最も右側（最大のインデックス + 1）の位置を返します。
  • bisect(a, x)はbisect_right(a, x)のエイリアスです。

import bisect

sorted_list = [1, 2, 4, 4, 5, 7]
pos_left = bisect.bisect_left(sorted_list, 4)
print(pos_left)  # 出力: 2

pos_right = bisect.bisect_right(sorted_list, 4)
print(pos_right)  # 出力: 4

insort_left と insort_right

• 引数:
  • a: ソート済みのリスト
  • x: 挿入したい値
  • lo: 挿入範囲の開始インデックス（デフォルトは0）
  • hi: 挿入範囲の終了インデックス（デフォルトはNone, リストの終端まで）
  • key: (Python 3.10 以降) 各要素を比較するための関数（デフォルトはNone）
• 動作:
  • insort_left(a, x): bisect_leftで取得した位置にxを挿入し、リストを維持したまま要素を追加します。
  • insort_right(a, x): bisect_rightで取得した位置にxを挿入し、リストを維持したまま要素を追加します。

import bisect

bisect.insort_left(sorted_list, 4)
print(sorted_list)  # 出力: [1, 2, 4, 4, 4, 5, 7]

bisect.insort_right(sorted_list, 4)
print(sorted_list)  # 出力: [1, 2, 4, 4, 4, 4, 5, 7]

注意点

ソート済みリストが前提

• bisectモジュールはソート済みのリストに対してのみ正しく動作します。
• 未ソートのリストに対して使用すると、予期しない動作をする可能性があります。

挿入コスト

• bisectを用いた検索はO(log N) ですが、実際の挿入操作 (insort_left や insort_right) はO(N) かかります。
• 大量のデータを扱う場合は、別のデータ構造（例: collections.deque や sortedcontainers）を検討するべきです。

key パラメータの使用

• Python 3.10以降では、keyパラメータを使ってカスタム比較が可能になりました。

import bisect

# 身長（cm）と名前のタプルのリスト（身長順にソート済み）
people = [(160, "Alice"), (165, "Bob"), (170, "Charlie"), (175, "David")]

# key パラメータを使用して、身長を基準に検索
height_to_find = 168
index = bisect.bisect_left(people, height_to_find, key=lambda x: x[0])

print(f"挿入位置: {index}")  # 身長168はBob(165)とCharlie(170)の間なので 2

# リストに身長 168 の新しい人を挿入
new_person = (168, "Eve")
people.insert(index, new_person)

print(people)
"""
実行結果
挿入位置: 2
[(160, 'Alice'), (165, 'Bob'), (168, 'Eve'), (170, 'Charlie'), (175, 'David')]
"""

まとめ

• bisectモジュールは、ソートされたリストに対して二分探索を行い、要素の挿入や検索位置の特定を効率的に行うための機能を提供します。
• 主な関数は以下のとおりです。
  • bisect_left(a, x): x を左側（最も前）の位置に挿入できるインデックスを取得
  • bisect_right(a, x): x を右側（最も後）の位置に挿入できるインデックスを取得
  • insort_left(a, x): リスト a に x を左側に挿入
  • insort_right(a, x): リスト a に x を右側に挿入
• 挿入そのものはリストの性質上O(N)となるため、大規模なデータや大量の挿入がある場合はデータ構造やアルゴリズムの選択を再考する必要があります。

ソートされたリストへの挿入が必要な場面では便利なモジュールなので、ぜひ活用してみてください。