Python:二分探索モジュールbisectについて

ども。AT274です。
今回は、「配列二分法アルゴリズム」モジュール「bisect」について紹介しようと思います。

このbisect、聞きなれた言葉でいうと、「二分探索」用のモジュールです。
あぁそれと、「二分探索は知ってるけど、bisectは知らない」人向けの記事になります。

「あー、はいはいbisectね！よゆーよゆー(ﾟ∀ﾟ)」って方は、記事の最後に簡単な確認問題へのリンク（AtCoder)を貼っているので暇つぶしにやってみるのもよいかもしれません。

まずはimport

とにもかくにもまずimportです。
bisectはLibパッケージに入っているのでそのまま書けます。
それと余談ですが、bisectは「～を二分する」という意味です。

import bisect

ついでに今回扱うリストも作っておきます。4がないのは仕様です。
それと、あらかじめソートしておく必要があります。

a = [1, 2, 3, 5, 6, 7, 8, 9]

挿入点を知る

まずは、挿入点を知るメソッドを紹介します。
試しに、欠けている4をどこに挿入すればいいかを聞いてみることにしましょう。
引数として、探索したいリストと挿入したい値を渡してあげます。

bisect.bisect_left(a, 4)
>>> 3

きちんと、リストの3番目に入ることを教えてくれていますね。

それでは次に5の入る場所を聞いてみます。aにはすでに5があるのですが、そのどちらにくるのか注目してください。

bisect.bisect_left(a, 5)
>>> 3

binsect_leftなので、既存の値の左側にきます。
そしてこれは、「既存の5がどこにあるのか探索したことと等しい」です。当たり前ですが。

leftがあるならrightもあります。

bisect.bisect_right(a, 5)
>>> 4

rightのほうを使うと、同じ値が見つかった場合にはその後ろを返します。
「ある値以下の数が何個あるのかを探す」のに役立ちます。
leftなら「ある値未満」ですネ。

挿入する

bisect_left(right)で、挿入すべきインデックスが分かったのでinsert文を使っても書くことはできます。
が、せっかくなのでbisectに備わっている挿入用メソッド「insort_left(right)」を使ってみましょう。

# 4は入ってません
# 左側
bisect.insort_left(a, 4)
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9]

# 右側
bisect.insort_right(a, 5)
>>> a
[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]

こんな感じですね。

確認問題

それでは確認問題です。AtCoder Biginner Contest 077のC問題となります。
「AtCoder登録してねぇよ！」って方はこの機会に登録してみてください。2分で終わります。（そして競技人口増えろ）
bisectを使うことですっきり解くことができますよ。（というか使わないと間に合わない）
C - Snuke Festival