はじめに
最近、Golangの練習がてら、AtCoderのコンテストに参加しています。全然いいパフォーマンスが出せておらず、まだ茶色コーダーですが、粘り強く頑張っていきます。
— n i s h i p y (@iamnishipy) August 22, 2020
普段はAtCoder Problemsで精進しています。解けなかった問題や、初めて使ったライブラリなどについて、このブログにメモを残すことにしました。より雑なメモや提出した解答例などは、GitHubにあげています。恥ずかしいのであまり見ないでください。
2分探索
2分探索は最も単純な探索アルゴリズムの1つで、Wikipediaによれば、「二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。」です。ソート済みの配列からある値を探索する際に、半分に絞り込むことを繰り返すことで、高速に処理します。
線形探索では\(O(N)\)かかる場合でも、二分探索を使えば\(O(log N)\)で探索できることが知られています。詳しくはけんちょんさんの記事をご覧ください。
Golangにおける二分探索
競プロでよく使われるC++ではstd::lower_bound()で、Pythonではbisect()で簡単に二分探索が利用できます。例えば、std::lower_bound()では、二分探索を行い、配列のうち値がkey以上となる最小のインデックスを返します。
Golangでも同様のものがないかと調べていたところ、sort.Search()が使えそうです。リファレンスには、以下のような説明があります。
- 二分検索を使用して、\(f(i)\) が \(true\)である\([0,n)\)の最小インデックス\(i\)を見つけて返します
- 最初に\(true\)となったときのインデックスを返す
- そのようなインデックスがない場合は、\(n\)を返す
\(f\)をうまく使えばいろいろ応用が効きそうです。リファレンスの例も載せておきます。ソート済み配列\(data\)から、\(data[i] \geq x\)を満たすような最初の\(x\)のインデックスを返します。
|
1 2 3 4 5 6 7 8 |
x := 23 i := sort.Search(len(data), func(i int) bool { return data[i] >= x }) if i < len(data) && data[i] == x { // x is present at data[i] } else { // x is not present in data, // but i is the index where it would be inserted. } |
ABC 143 D – Triangles を解く
問題
こちらを参照。
Golangでの実装例
解説記事 AtCoder ABC 143 D – Triangles (400 点) – けんちょんの競プロ精進記録の「解法 1： 二分探索」を参考に、Golangで実装しました。C++のlower_boundの代わりに、前述の通り、sort.Search()を使っただけです。
無駄なコードが多いので、抜粋して載せます。
全体はこちらです。
以上.
コメント