目次
～ ライブラリ ～
まずは使用するライブラリをインポート import bisect
bisectとは （もしかして：array）
bisectを利用した二分探索
～ 自作の関数 ～
指定した数字以下で最大の要素を求める場合
指定した数字以上で最小の要素を求める場合
はじめに
チートシートの扱いついてはここを読んでください
仕組みを理解してれば実装は簡単だけど、単純に書くのが面倒だし地味によく必要になるので、必要な時に積極的に使うよう促すべくチートシートを用意しておく
bisectとは
bisect はPythonの標準ライブラリの１つ
本来はソートされた配列に要素を追加するときに追加後に再度ソートし直さなくて済むよう、要素を追加するべき場所を返す関数だが、これを利用することで配列内を二分探索するのに使うことが可能
import bisect
# 0 1 2 3 4 5 6 7 8 9
# v v v v v v v v v v
mat = [ 0 , 1 , 2 , 3 , 3 , 3 , 3 , 4 , 5 ]
print(bisect.bisect_left(mat, 3))
print(bisect.bisect_right(mat, 3))
print(bisect.bisect(mat, 3))
>>> 3
>>> 7
>>> 7
追加する要素と同じ要素が配列にある場合、それらよりも左側に挿入したければ bisect.bisect_left() 、それらよりも右側に挿入したければ bisect.bisect_right() を用いる
bisect.bisect() は実質 bisect.bisect_right()
import bisect
mat = [0, 1, 2, 3, 3, 3, 4, 5]
bisect.insort_left(mat, 3)
bisect.insort_right(mat, 3)
bisect.insort(mat, 3)
v
>>> [0, 1, 2, 3, 3, 3, 3, 4, 5]
v
>>> [0, 1, 2, 3, 3, 3, 3, 3, 4, 5]
v
>>> [0, 1, 2, 3, 3, 3, 3, 3, 3, 4, 5]
bisect.bisect_left() , bisect.bisect_right() , bisect.bisect() で指定した位置に要素を挿入できる
bisect.bisect() と .insert() を組み合わせたものと同じ
配列の途中に要素を何度も追加する場合には、listではなくarrayを利用することで高速に処理でき幸せになれる場合がある
bisectを利用した二分探索
import bisect
# 0 1 2 3 4 5 6 7 8 9
mat = [0, 1, 2, 3, 3, 3, 3, 4, 5, 6]
print(bisect.bisect(mat, 2)-1) # 要素１つを探索する場合
print(bisect.bisect_left(mat, 3)) # 指定した数字以上で最小の要素
print(bisect.bisect_right(mat, 3)-1) # 指定した数字以下で最大の要素
print(bisect.bisect_left(mat, 3)-1) # 指定した数字未満で最大の要素
print(bisect.bisect_right(mat, 3)) # 指定した数字より大きい最小の要素
print(bisect.bisect_left(mat, 3), bisect.bisect_right(mat, 3)-1) # 要素の範囲を探索する場合
>>> 2 # 要素１つを探索する場合
>>> 3 # 指定した数字以上で最小の要素
>>> 6 # 指定した数字以下で最大の要素
>>> 2 # 指定した数字未満で最大の要素
>>> 7 # 指定した数字より大きい最小の要素
>>> 3 6 # 要素の範囲を探索する場合
bisect.bisect() は指定した数字を新たに要素として追加する場合の挿入位置なので、元の配列の要素の位置を考えると -1 する必要があったりなかったりする
配列に調べたい数字が含まれている場合
mat = [1,2,3,5,8,13,21]
def nibutan(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] < NUM:
MIN = TMP
elif MAT[TMP] > NUM:
MAX = TMP
elif MAT[TMP] == NUM:
MIN = TMP
break
if MAX-MIN <= 1:
break
if MAT[MIN] != NUM:
MIN = MAX
return MIN # ,MAT[MIN]
print(nibutan(8,mat))
>>> 4
MATのソートを忘れずに
指定した数字以下で最大の要素を求める場合
mat = [1,2,3,5,8]
def nibutan_ika(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] <= NUM:
MIN = TMP
elif MAT[TMP] > NUM:
MAX = TMP
if MAX-MIN <= 1:
break
if MAT[MAX] <= NUM:
MIN = MAX
return MIN #,MAT[MIN]
for i in range(10):
print(i,nibutan_ika(i,mat))
>>> 0 0
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 2
>>> 5 3
>>> 6 3
>>> 7 3
>>> 8 4
>>> 9 4
指定した数字がMAT[0]より小さい場合、注意が必要
指定した数字未満で最大の要素を求める場合は以下のコード（=の位置をいじっただけ）
mat = [1,2,3,5,8]
def nibutan_mimann(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] < NUM:
MIN = TMP
elif MAT[TMP] >= NUM:
MAX = TMP
if MAX-MIN <= 1:
break
if MAT[MAX] < NUM:
MIN = MAX
return MIN #,MAT[MIN]
for i in range(10):
print(i,nibutan_mimann(i,mat))
>>> 0 0
>>> 1 0
>>> 2 0
>>> 3 1
>>> 4 2
>>> 5 2
>>> 6 3
>>> 7 3
>>> 8 3
>>> 9 4
指定した数字以上で最小の要素を求める場合
mat = [1,2,3,5,8]
def nibutan_ijyou(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] < NUM:
MIN = TMP
elif MAT[TMP] >= NUM:
MAX = TMP
if MAX-MIN <= 1:
break
if MAT[MIN] >= NUM:
MAX = MIN
return MAX #,MAT[MIN]
for i in range(10):
print(i,nibutan_ijyou(i,mat))
>>> 0 0
>>> 1 0
>>> 2 1
>>> 3 2
>>> 4 3
>>> 5 3
>>> 6 4
>>> 7 4
>>> 8 4
>>> 9 4
指定した数字がMAT[-1]より大きい場合、注意が必要
指定した数字より大きくて最小の要素を求める場合は以下のコード（=の位置をいじっただけ）
mat = [1,2,3,5,8]
def nibutan_yoridai(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] <= NUM:
MIN = TMP
elif MAT[TMP] > NUM:
MAX = TMP
if MAX-MIN <= 1:
break
if MAT[MIN] > NUM:
MAX = MIN
return MAX #,MAT[MIN]
for i in range(10):
print(i,nibutan_yoridai(i,mat))
>>> 0 0
>>> 1 1
>>> 2 2
>>> 3 3
>>> 4 3
>>> 5 4
>>> 6 4
>>> 7 4
>>> 8 4
>>> 9 4
要素が指定した数字である範囲を求める場合
mat = [0,1,2,2,2,2,3,4]
def nibutan_ika(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] <= NUM:
MIN = TMP
elif MAT[TMP] > NUM:
MAX = TMP
if MAX-MIN <= 1:
break
if MAT[MAX] <= NUM:
MIN = MAX
return MIN #,MAT[MIN]
def nibutan_ijyou(NUM,MAT):
MIN = 0
MAX = len(MAT)-1
while True:
TMP = (MIN+MAX)//2
if MAT[TMP] < NUM:
MIN = TMP
elif MAT[TMP] >= NUM:
MAX = TMP
if MAX-MIN <= 1:
break
if MAT[MIN] >= NUM:
MAX = MIN
return MAX #,MAT[MIN]
print(nibutan_ijyou(2,mat), nibutan_ika(2,mat))
>>> 2 5
指定した数字以下で最大の要素を求める場合 と 指定した数字以上で最小の要素を求める場合 を組み合わせればいい
二分探索で下限を求めた後、次の数字になるまで愚直にwhile文で +1 し続けて調べるみたいな雑な探索をしないこと！（他の探索の場合も）