競プロって何ですか？

14. これが二分探索ですか？

　競技プログラミング部の部室にはいつもの4人がいる。

　全開の窓から気持ちの良い風が入り込んでくる。この部室には空調設備はないが、夏になっても快適に過ごせる気がした。

「じゃあ今日は二分探索について勉強しようか」

　枝刈先輩がいつものようにホワイトボードの前に立っていた。私と早希、玲奈は椅子に座ってその先輩の授業を聞いていた。

「二分探索……本にそんな名前が出てきたような」

　私は家で読んでいる競技プログラミングの本を思い出す。たしかに「二分探索」という名前には覚えがある。しかし、どんなアルゴリズムだったかはまでは思い出せない。というかそもそも理解できなかった。

「あれ？　じゃあ教えなくても大丈夫？」

　枝刈先輩が困った表情を浮かべたので、私は慌てて訂正する。

「いえいえ、本を読んでも理解できなかったのでぜひ教わりたいです」

「そうなのね。じゃあまずはこの問題を解いてみて」

　枝刈先輩がホワイトボードにすらすらと問題を書いていく。

◇◇◇◇◇◇

太郎君はN個の整数A_0, A_1, ……, A_N-1を持っています。A_i >= Mであるようなiのうち、最小のものを求めなさい。

制約

1 <= N <= 10^5

0 <= M <= 10^9

0 <= A_i <= 10^9

入力

N　M

A_0, A_1, ……, A_N-1

出力

A_i >= Mであるようなiのうち、最小のものを出力せよ。

◇◇◇◇◇◇

　問題を見て早希が「おっ」と声をあげる。

「線形探索で解けそうだけど、この問題。二分探索は関係ないの？」

「まあまあ、とりあえず解いてみて」

　私も少し考えて、この問題が線形探索で解けることが分かった。まず入力を受け取ったら数列Aを昇順にソートする。あとは前から順に調べていって、A_i >= Mとなるタイミングを見つければいいのだ。

「書けた……」

　コードを提出すると、少しの後、「AC」が表示された。

「解けました」

「私も解けたぜ」

「私も」

　私と早希、玲奈は無事にこの問題を解くことができた。しかし、なぜ枝刈先輩がこんな問題を出題したのか、その意図が分からない。

「みんな解けたみたいね。それじゃあこの問題の別解について考えてみようか」

「別解？」

「そう、別解。この問題はもっと高速に解くことができるんだ」

「それが二分探索ってこと？」

「そういうこと。たとえばこんなふうに書くことができる」

　枝刈先輩はまたしてもすらすらとホワイトボードにコードを書いていく。

◆◆◆◆◆◆

#include <bits/stdc++.h>

using namespace std;

int main() {

　// 入力の受け取り

　int n, m;

　cin >> n >> m;

　vector<int> a(n);

　for(int i = 0; i < n; ++i) cin >> a[i];

　// 昇順にソート

　sort(a.begin(), a.end());

　// 二分探索

　int left = -1;

　int right = n;

　while(right-left > 1) {

　　int mid = (left+right) / 2;

　　if(a[mid] >= m) right = mid;

　　else left = mid;

　}

　// 答えを出力

　cout << right << endl;

}

◆◆◆◆◆◆

　私はそのコードを理解できなかった。昇順にソートするところまでは私が書いたコードと同じだ。その後に続く二分探索が理解できない。

「二分探索っていうのは、探索範囲を半分に絞り込む過程を繰り返すことで、目的の値を見つける探索方法のことだよ」

「半分に？　どういうことですか？」

「たとえば、このコードではまずiが取り得る範囲をleftとrightとしている。その後、leftとrightの中間点midを求める。そして答えとなる値がmid以上が未満かを判定して、探索範囲を半分に絞り込む。これを繰り返す」

　枝刈先輩は「図に書くとこうだね」と言いながらホワイトボードに図を書いてくれた。その図を見てようやく、なんとなくだが理解できた気がする。まだ問題を解いていないから何とも言えないけど。

「ということで、さっきの問題を今度は二分探索を使って解いてみて」

　私は先輩が書いたコードを真似てコードを書いてみた。そのコードを提出するとちゃんと「AC」できた。

　別解で解くという経験は初めてだったので、何とも言えない感覚を味わった。同じ問題でも解き方は一つではないということだろうか。

「二分探索、おもしろいな。他に問題ないの？」

　早希がそう尋ねると、枝刈先輩が笑った。

「そう言うと思って二分探索の問題をピックアップしておいたよ。全部で10問。今日はこの問題を全部解けたら帰ってよし」

　それから私と早希、玲奈は枝刈先輩がピックアップした二分探索10問を解き続けた。いつの間にか日は暮れ、5時のチャイムが鳴っていた。

　長時間頭を使い続けたので、とても疲れた。お腹も空いた。だけども充実した一日だったと感じる。また一つ賢くなった。二分探索を覚えたことで解ける問題も増えたはずだ。そのことが嬉しくてたまらない。次のコンテストが待ち遠しくなった。

■■■つづく■■■