W3C SVG

Python 標準ライブラリ bisect 配列二分法

  1. まるさんかくしかく　Tech学習と入門ログ
  2. Python
  3. Python標準のライブラリ
  4. Python 標準ライブラリ bisect 配列二分法
2021-03-29

配列二分法で挿入位置の取得や挿入を行う事をサポートするライブラリです。

bisect 配列二分法の使い方

import bisect

items = [1, 2, 3, 3, 3, 5, 6, 6, 7, 9]

# bisect_right(a, x, lo=0, hi=len(a)) リストaに順序を保ったままxを挿入できる位置を取得
# bisect(a, x, lo=0, hi=len(a)) リストaに順序を保ったままxを挿入できる位置を取得
# すでにxがaに含まれる場合右端の位置
# lo:開始位置
# hi:終了位置
bisect.bisect_right(items, 4) # => 5
all(v <= 4 for v in items[0:5]) # => True
all(v > 4 for v in items[5:]) # => True

bisect.bisect_right(items, 6) # => 8
all(v <= 6 for v in items[0:8]) # => True
all(v > 6 for v in items[8:]) # => True

# bisect_left(a, x, lo=0, hi=len(a)) リストaに順序を保ったままxを挿入できる位置を取得
# すでにxがaに含まれる場合左端の位置
# lo:開始位置
# hi:終了位置
bisect.bisect_left(items, 4) # => 5
all(v < 4 for v in items[0:5]) # => True
all(v >= 4 for v in items[5:]) # => True

bisect.bisect_left(items, 6) # => 6
all(v < 6 for v in items[0:6]) # => True
all(v >= 6 for v in items[6:]) # => True

# insort_right(a, x, lo=0, hi=len(a)) リストaに要素xを順序を保ったまま挿入
# insort(a, x, lo=0, hi=len(a)) リストaに要素xを順序を保ったまま挿入
# すでにxがaに含まれる場合右端の位置
# lo:開始位置
# hi:終了位置
bisect.insort_right(items, 4)
items # => [1, 2, 3, 3, 3, 4, 5, 6, 6, 7, 9]

# insort_left(a, x, lo=0, hi=len(a)) リストaに要素xを順序を保ったまま挿入
# すでにxがaに含まれる場合左端の位置
# lo:開始位置
# hi:終了位置
bisect.insort_left(items, 6)
items # => [1, 2, 3, 3, 3, 4, 5, 6, 6, 6, 7, 9]

参考