ソートされたリストの二分探索 - 競プロPythonのスニペット置き場

長さ $N$ の数列に対して、以下のことを行える。

$O(N\log N)$ 　前処理　昇順ソートする

$O(\log N)$ $x$ 以上の/以下の/より大きい/より小さい要素の個数
$O(\log N)$ $x$ 以上の/より大きい要素のうち最小のindex
$O(\log N)$ $x$ 以下の/より小さい要素のうち最大のindex

l.sort()

from bisect import bisect_left,bisect_right

count_x_or_more_than_x=len(l)-bisect_left(l,x)      # x以上の要素の個数
count_more_than_x=len(l)-bisect_right(l,x)          # xより大きい要素の個数
count_x_or_less_than_x=bisect_right(l,x)            # x以下の要素の個数
count_less_than_x=bisect_left(l,x)                  # xより小さい要素の個数

# if index=len(l): 存在しない
index_x_or_more_than_x=bisect_left(l,x)             # x以上の要素のうち最小のindex
index_more_than_x=bisect_right(l,x)                 # xより大きい要素のうち最小のindex

# if index=-1: 存在しない
index_x_or_less_than_x=bisect_right(l,x)-1          # x以下の要素のうち最大のindex
index_less_than_x=bisect_left(l,x)-1                # x未満の要素のうち最大のindex

例題

参考