Pythonのbisectモジュール

Pythonのbisectモジュールは、リストを再ソートすることなく、リストに要素を挿入した後、リストの秩序状態を維持することができます.bisectには、同じパラメータを受け入れる6つの関数があります.

bisect.bisect_left(a,x,lo=0,hi=len(a):aはリストであり、xは挿入する要素である.関数は、aにxが挿入された位置を返し、aにxが保存されている場合、挿入された位置はaの一番左のxの前のビットになります.戻り値はリストを2つの部分に分け,挿入点左側がall(val=x for val in a[i:hi])を満たす.

bisect.bisect_right(a,x,lo=0,hi=len(a):bisect.bisect_leftの違いは、aにxが既に存在する場合、挿入された位置がaの最も右側のxの後ろにあることである.

bisect.bisect(a,x,lo=0,hi=len(a):bisect.bisect_rightは同じです.戻り値はリストを2つの部分に分け,挿入点左側がall(val<=x for val in a[lo:i+1]),挿入点右側がall(val>x for val in a[i+1:hi])を満たす.

bisect.insort_left(a,x,lo=0,hi=len(a):要素を挿入したリストを返します.まずbisectを使用します.bisect_leftは、エレメントを挿入する場所を取得し、その場所にエレメントを挿入してリストに戻ります.a.insert(bisect.bisect_left(a,x,lo,hi),x)と等価である.

bisect.insort_right(a,x,lo=0,hi=len(a):a.insert(bisect.bisect_right(a,x,lo,hi),x)に等価である.

bisect.insort(a,x,lo=0,hi=len(a):a.insert(bisect.bisect(a,x,lo,hi),x)に等価である.

例:

li = [1, 3, 5, 7, 9]
print(bisect.bisect_left(li, 6))
print(bisect.bisect_right(li, 6))
print(bisect.bisect(li, 6))

# Output:
3
3
3

bisect.insort_left(li, 6)
print(li)
bisect.insort_right(li, 4)
print(li)
bisect.insort(li, 8)
print(li)

# Output:
[1, 3, 5, 6, 7, 9]
[1, 3, 4, 5, 6, 7, 9]
[1, 3, 4, 5, 6, 7, 8, 9]

li = [1, 3, 4, 4, 4, 7, 8]
print(bisect.bisect_left(li, 4))
print(bisect.bisect_right(li, 4))
print(bisect.bisect(li, 4))

# Output:
2
5
5

bisect.insort_left(li, 4)
print(li)
bisect.insort_right(li, 4)
print(li)
bisect.insort(li, 4)
print(li)

# Output:
[1, 3, 4, 4, 4, 4, 7, 8]
[1, 3, 4, 4, 4, 4, 4, 7, 8]
[1, 3, 4, 4, 4, 4, 4, 4, 7, 8]