bisectのleftとrightで混乱したときに見る場所 - isee競プロメモ

bisectのleftとrightで混乱したときに見る場所

結論

$ A_i \ge x となる最小の添字$ i → _left

$ A_i \gt x となる最小の添字$ i → _right

※$ \forall i \colon A_i < x だと配列の外側len(A)を指す

$ A_i \lt x となる最大の添字$ i → _left - 1

$ A_i \le x となる最大の添字$ i → _right - 1

※$ \forall i \colon A_i > x だと配列の外側-1を指す

$ A_i \lt x となる$ A_i の個数 → _left

$ A_i \le x となる$ A_i の個数 → _right

実験

一旦落ち着いて以下のコードを試してみる

code:bisect_test.py

import bisect

A = 1, 2, 2, 2, 3, 5

x = 2

y = 4

# 同じ値があるとき指す場所

print(bisect.bisect_left(A, x)) # > 1

print(bisect.bisect_right(A, x)) # > 4

# 同じ値がないとき指す場所

print(bisect.bisect_left(A, y)) # > 5

print(bisect.bisect_right(A, y)) # > 5

つまり、_left_rightそれぞれの指す場所は

code:explain

対象： 2

1 2 2 2 3 5

^ ^

_left _right