Goで二分探索 sort.Search()を使う[ABC 143 D – Triangles]

Golang

はじめに

最近、Golangの練習がてら、AtCoderのコンテストに参加しています。全然いいパフォーマンスが出せておらず、まだ茶色コーダーですが、粘り強く頑張っていきます。

普段はAtCoder Problemsで精進しています。解けなかった問題や、初めて使ったライブラリなどについて、このブログにメモを残すことにしました。より雑なメモや提出した解答例などは、GitHubにあげています。恥ずかしいのであまり見ないでください。

nishipy/kyopuro
精進の記録. Contribute to nishipy/kyopuro development by creating an account on GitHub.

2分探索

2分探索は最も単純な探索アルゴリズムの1つで、Wikipediaによれば、「二分探索(にぶんたんさく、英: binary search、BS)やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。」です。ソート済みの配列からある値を探索する際に、半分に絞り込むことを繰り返すことで、高速に処理します。

線形探索では\(O(N)\)かかる場合でも、二分探索を使えば\(O(log N)\)で探索できることが知られています。詳しくはけんちょんさんの記事をご覧ください。

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita
0. はじめに 二分探索法は単純ながらも効果が大きく印象に残りやすいもので、アルゴリズム学習のスタート地点に彩られた花という感じです。二分探索というと「ソート済み配列の中から目的のものを高速に探索する」アルゴリズムを思い浮かべる...

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\)のインデックスを返します。



ABC 143 D – Triangles を解く

問題

こちらを参照。

Golangでの実装例

解説記事 AtCoder ABC 143 D – Triangles (400 点) – けんちょんの競プロ精進記録の「解法 1: 二分探索」を参考に、Golangで実装しました。C++のlower_boundの代わりに、前述の通り、sort.Search()を使っただけです。

無駄なコードが多いので、抜粋して載せます。

全体はこちらです。

nishipy/kyopuro
精進の記録. Contribute to nishipy/kyopuro development by creating an account on GitHub.

以上.

コメント