リストからL以上R以下を取り出す

きっかけ

範囲指定のあるクエリを処理していくタイプの問題で、以上以下の条件を満たす個数だったり要素だったりを集計することがあります。その問題対策用の個人的なメモです。

注意点

高速化を考えてみたのですが、二分探索でのゴリ押ししか思い浮かびませんでした。
なので、配列をソートしている必要があります。なにかいいアイデアがあったら教えてください。。。

また、コンテストでの利用などは自己責任でお願いいたします。

コード

from bisect import bisect_left,bisect_right

#任意の数列
seq = [3,5,8,9,12,12,22,23,30]

def LR_calc(L,R,seq):
    # L以上R以下の要素の個数と、切り出したリストを返す
    return bisect_right(seq,R)-bisect_left(seq,L),seq[bisect_left(seq,L):bisect_right(seq,R)]

# すべて取り出す
print(LR_calc(2,31,seq))
print(LR_calc(3,30,seq))
# (9, [3, 5, 8, 9, 12, 12, 22, 23, 30])
# (9, [3, 5, 8, 9, 12, 12, 22, 23, 30])

# チェック
print(LR_calc(4,8,seq))
print(LR_calc(4,9,seq))
print(LR_calc(4,10,seq))
print(LR_calc(5,8,seq))
print(LR_calc(5,9,seq))
print(LR_calc(5,10,seq))
# (2, [5, 8])
# (3, [5, 8, 9])
# (3, [5, 8, 9])
# (2, [5, 8])
# (3, [5, 8, 9])
# (3, [5, 8, 9])

# 存在しない要素、重複している要素部分のチェック
print(LR_calc(7,7,seq))
print(LR_calc(7,8,seq))
print(LR_calc(8,8,seq))
print(LR_calc(12,12,seq))
print(LR_calc(9,12,seq))
print(LR_calc(12,22,seq))
print(LR_calc(9,22,seq))
# (0, [])
# (1, [8])
# (1, [8])
# (2, [12, 12])
# (3, [9, 12, 12])
# (3, [12, 12, 22])
# (4, [9, 12, 12, 22])

# リストのはじまりを含む場合のチェック
print(LR_calc(2,4,seq))
print(LR_calc(2,5,seq))
print(LR_calc(3,4,seq))
print(LR_calc(3,5,seq))
# (1, [3])
# (2, [3, 5])
# (1, [3])
# (2, [3, 5])

# リストのおわりを含む場合のチェック
print(LR_calc(23,30,seq))
print(LR_calc(23,31,seq))
print(LR_calc(24,30,seq))
print(LR_calc(24,31,seq))
# (2, [23, 30])
# (2, [23, 30])
# (1, [30])
# (1, [30])