はじめに
~bisect_leftを使うたびに頭が爆発しているあなたへ~
bisect_left / bisect_right 関数は、bisectモジュールに用意されている、二分探索を用いて要素が配列の中の何番目かを取得することが出来る関数です。
競技プログラミングなどで、"○○以下の要素が何個か"などを高速に求めたい時、よく使用します。
ただ、「この値を入れたらどんな値が返ってくるか」 や
「値が配列に含まれている時はどんな値が返ってくるか」 など
使うたびに頭が爆発していませんか？
この記事は、そんなあなたに向けた記事です。
これを見ればもう迷うことはないでしょう。
この記事の対象読者
この記事を読んでいる段階は以下とします。
- 二分探索を理解していて、
bisect_leftも使ったことがある - 問題の考察を終わらせて、あとは
bisect_leftを使うだけ -
bisect_leftを使うたびに頭が爆発している
「二分探索って何？」って方は他の方の二分探索の記事をご覧ください。
二分探索は競技プログラミングにおける脱初心者のためのアルゴリズムなので、是非じっくり勉強してみてください。とても面白いアルゴリズムですよ。
本編
bisect_leftで悩むシチュエーション（N回目）
コンテスト中にbisect_leftを使うと良さそうというのが分かった。
しかし、あなたはこんな風に悩んでいるかもしれません。
具体例を上げましょう。このようなlistがあったとします。
li = [0, 5, 10, 15]
ここで以下の関数の戻り値はいくつになるでしょうか？
考えてみてください。ぱっと見てわかるでしょうか？
bisect_left(li, 3)
ぱっと見でわかる方はこの記事を読む必要はありません。
さっさとコンテストに戻って実装を進めて提出してください。
「3は0より大きくて、5より小さいから...」
「0のindexが0だから...」
など考えたかもしれません。
それなら、これはどうでしょうか？
bisect_left(li, 5)
「listの要素に含まれる値の場合はどうなるんだっけ？」
「5のindexが1だから1？」
引数の値が要素に含まれる場合もややこしいですね。
最後にこんなのはどうでしょうか？
bisect_right(li, 3)
「leftじゃなくてrightになったらどうなるんだっけ?」
「rightって何が右やねん...」
こうなるともうわからない。
こうしてボクのようにコンテスト中に頭が爆発し、ちまちまprint()でテストして時間を無駄にするのです。
しかし、これを一発でわかる魔法のような図があります。
bisect_leftが一発でわかるようになる図
最初に本質を伝えます。
bisect_leftは値のindexを返す関数ではありません。
bisect_leftは値の間のindex を返す関数です。
数直線を書いて考えてみましょう。
li = [0, 5, 10, 15]
このlistを数直線上に表してみるとこうなります。
ここで、値ではなく値の間の区間に番号を付けてみます
listの要素が4つなので、区間は5つになります。
実はこの図を見たあなたは、もうbisect_leftに迷うことは無くなりました。
同じ問題を見てみましょう
bisect_left(li, 3)
この関数が返す値は図を見れば一瞬でわかります。数直線上の紫の区間のうち、3はどの箇所にあるでしょうか？
そうです、区間1ですね。bisect_left(li, 3)も1を返します
さらに、bisect_right(li, 3)も戻り値は1です
bisect_left(li, 3) # 1
bisect_right(li, 3) # 1
図をイメージした途端に、とても分かりやすくなったのではないでしょうか？
listの要素に含まれない値を検索した時は、bisect_left、bisect_rightどちらも同じ値を返します
bisect_leftとbisect_rightの違いは、listに含まれる要素を検索した時に現れます
bisect_leftとbisect_rightの違い
違いが表れる例を示します
bisect_left(li, 5) # 1
bisect_right(li, 5) # 2
listに含まれる要素の5で検索すると違いが表れます。
もう一度図を見てみましょう。
この図を見ると区間１と区間２はどちらも5という数字を含んでいます。
bisect_leftとbisect_rightの違いは、含まれる区間が2つある時に
どちらの区間に含まれることにするかという違いになります。
bisect_leftは、5の左の区間1。
bisect_rightも同様に、5の右の区間2に含まれる判定をします。
関数名を考えた方は大変センスがありますね。
この図を元に関数名を付けたかは定かではありませんが、leftとrightの意味をこのように理解しておくと正しく実装できそうです。
また、bisect_leftは区間を半開半閉区間、bisect_rightは区間を半閉半開区間と捉えているとも言えるかもしれません。
おわりに
一番大切なのは、bisect_leftは値のindexを返すのではなく、値の間の区間のindexを返す関数だということです。
これを覚えておけばこれから先、bisect_leftとbisect_rightのどちらを使えば良いのかの見当をつけやすくなると思います。
さあ、理解出来たら早くコンテストに戻ってください。こんな文章を読んでいる間にコンテストの時間は進んでいますよ。
それでは、さようなら。あなたのお役に立てれば幸いです。