はじめに
最近、Golangの練習がてら、AtCoderのコンテストに参加しています。全然いいパフォーマンスが出せておらず、まだ茶色コーダーですが、粘り強く頑張っていきます。
— n i s h i p y (@iamnishipy) August 22, 2020
普段はAtCoder Problemsで精進しています。解けなかった問題や、初めて使ったライブラリなどについて、このブログにメモを残すことにしました。より雑なメモや提出した解答例などは、GitHubにあげています。恥ずかしいのであまり見ないでください。
![](https://nishipy.com/wp-content/uploads/cocoon-resources/blog-card-cache/f543dc43b7b380979be974b14c3fd120.png)
2分探索
2分探索は最も単純な探索アルゴリズムの1つで、Wikipediaによれば、「二分探索(にぶんたんさく、英: binary search、BS)やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。」です。ソート済みの配列からある値を探索する際に、半分に絞り込むことを繰り返すことで、高速に処理します。
線形探索では\(O(N)\)かかる場合でも、二分探索を使えば\(O(log N)\)で探索できることが知られています。詳しくはけんちょんさんの記事をご覧ください。
![](https://qiita-user-contents.imgix.net/https%3A%2F%2Fcdn.qiita.com%2Fassets%2Fpublic%2Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png?ixlib=rb-4.0.0&w=1200&mark64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9JUU0JUJBJThDJUU1JTg4JTg2JUU2JThFJUEyJUU3JUI0JUEyJUUzJTgyJUEyJUUzJTgzJUFCJUUzJTgyJUI0JUUzJTgzJUFBJUUzJTgyJUJBJUUzJTgzJUEwJUUzJTgyJTkyJUU0JUI4JTgwJUU4JTg4JUFDJUU1JThDJTk2JTIwJUUzJTgwJTlDJTIwJUUzJTgyJTgxJUUzJTgxJTkwJUUzJTgyJThCJUU1JUJDJThGJUU0JUJBJThDJUU1JTg4JTg2JUU2JThFJUEyJUU3JUI0JUEyJUU2JUIzJTk1JUUzJTgxJUFFJUUzJTgyJUI5JUUzJTgyJUI5JUUzJTgzJUExJTIwJUUzJTgwJTlDJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnR4dC1jb2xvcj0lMjMxRTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmcz1mNTMyY2MyOTJhNjIwYWQ0MDBmNjUwNWVlYjJjZDhhNA&mark-x=142&mark-y=57&blend64=aHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBkcmtlbiZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ZWZjMDkzYzVlNmUwZjc4NzQ3N2IwNjQ5OTI1ZWQyMGM&blend-x=142&blend-y=436&blend-mode=normal&txt64=aW4g5qCq5byP5Lya56S-TlRU44OH44O844K_5pWw55CG44K344K544OG44Og&txt-width=770&txt-clip=end%2Cellipsis&txt-color=%231E2121&txt-font=Hiragino%20Sans%20W6&txt-size=36&txt-x=156&txt-y=536&s=42988a27212e3e5b20d6a63e7330e7cf)
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()
を使っただけです。
無駄なコードが多いので、抜粋して載せます。
全体はこちらです。
![](https://nishipy.com/wp-content/uploads/cocoon-resources/blog-card-cache/f543dc43b7b380979be974b14c3fd120.png)
以上.
コメント