zuka二分探索を実装するよ。
本記事では，二分探索の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。
本記事の概要
まずは，二分探索のお気持ちをお伝えしていきます。その次に，二分探索の雛形となる実装，そして最後により汎用的な実装方法をお伝えしていきます。
二分探索のお気持ち
汎用的な実装
お気持ち
二分探索は，ソートされた配列において条件を満たす要素を探し出すアルゴリズムの1つです。要素を調べる範囲を半分ずつに絞っていくことから二分探索と呼ばれています。全てをしらみつぶしに調べると$O(N)$かかってしまうような場合でも，対象範囲を各探索ステップごとに半分にしていくため，$O(\log N)$まで抑えることができる有能なアルゴリズムです。
このアルゴリズムですが，基本的な場合だと「ピンポイント」の条件を考えることが多いです。しかし，本記事ではピンポイントを「領域」へ拡張することで，より汎用的な二分探索の使い方をお伝えしていきます。
zukaピンポイントから領域への拡張は累積和の考え方と同じだよ。これから具体例を見ていくね。
基本的な実装
素直に二分探索を実装すると以下のようになります。例題として，以下のような問題を考えてみましょう。
{1,3,5,7,9}において7は何インデックス目か
#include <bits/stdc++.h>
using namespace std;
// 二分探索する関数
// 引数はvector
int binary_search(vector<int> X, int key) {
int left = 0; // 配列の左端
int right = X.size() - 1; // 配列の右端
// 両端の差が一致するまで続ける
while (right - left >= 1){
int mid = left + (right - left) / 2; // 区間の真ん中
if (X[mid] == key) return mid; // もし調べている対象が「条件」そのものであればindexを返す
else if (X[mid] > key) right = mid - 1; // もし調べている対象が「条件」である対象よりも大きければ右端を移動
else if (X[mid] < key) left = mid + 1; // もし調べている対象が「条件」である対象よりも小さければ左端を移動
}
return -1;
}
vector<int> X = {1, 3, 5, 7, 9};
int main(){
cout << binary_search(X, 7) << endl; // 3を返す
}
{1,3,5,7,9}における7のインデックスが得られたね。
発展的な実装
さて，ここからは二分探索をもう少し汎用的なアルゴリズムとして捉えてみましょう。さきほど，二分探索は「ソートされた配列において条件を満たす要素を探し出す」アルゴリズムだと説明しました。
そこで例題を振り返ってみると，実は{1,3,5,7,9}における7のインデックスを求めるという問題は，以下のように2つの捉え方ができるのです。
{1,3,5,7,9}において7と等しい要素のインデックスを見つける（ピンポイント）{1,3,5,7,9}において7以上である要素のうち最小のインデックスを見つける（領域）
これらの問題において，条件部分を抽出すると以下のようになります。
7と等しい（ピンポイント）7以上である（領域）
この2つの捉え方のそれぞれにおいて，leftインデックスとrightインデックスの役割が変わってきます。
leftとrightは調べる範囲のインデックス。left=rightになるまで繰り返す。leftは条件を満たさない最大のインデックス。rightは条件を満たす最小のインデックス。right-left=1になるまで繰り返す。
これらの条件判定部分をis_ok関数として分離して，再び二分探索を実装してみたいと思います。
まずは問題を1番目の条件として捉えたものです。leftインデックスとrightインデックスは単に区間の両端を表しているだけという点に注意してください。
#include <bits/stdc++.h>
using namespace std;
bool is_ok(int x, int y){
return x == y;
}
// 二分探索する関数
// 引数vectorバージョン
int binary_search(vector<int> X, int key) {
int left = 0; // 配列の左端
int right = X.size() - 1; // 配列の右端
// 両端の差が一致するまで続ける
while (right - left >= 1){
int mid = left + (right - left) / 2; // 区間の真ん中
if (is_ok(X[mid], key)) return mid; // もし調べている対象が「条件」そのものであればindexを返す
else if (X[mid] > key) right = mid - 1; // もし調べている対象が「条件」である対象よりも大きければ右端を移動
else if (X[mid] < key) left = mid + 1; // もし調べている対象が「条件」である対象よりも小さければ左端を移動
}
return -1;
}
vector<int> X = {1, 3, 5, 7, 9};
int main(){
cout << binary_search(X, 7) << endl;
}
if文の中身をis_okに変えただけだね。
続いて，問題を2番目の条件として捉えたものです。leftインデックスは「条件を満たさない最大のインデックス」でしたので，初期値には-1を入れます。なぜなら，インデックス0が条件を満たす場合があるからです。そのような場合には，右端が最終的にインデックス0になるので，leftインデックスとしてはその1つ手前の-1で待機している必要があります。
同様に，rightインデックスは「条件を満たす最大のインデックス」でしたので，初期値には配列の長さを入れます。なぜなら，配列の末尾が条件を満たす場合があるからです。そのような場合には，左端が最終的に配列の末尾インデックスになるので，rightインデックスとしては配列の末尾インデックスの1つ後に待機している必要があります。
#include <bits/stdc++.h>
using namespace std;
bool is_ok(int x, int y){
return x >= y;
}
// 二分探索する関数
// 引数vectorバージョン
int binary_search(vector<int> X, int key) {
int left = -1; // 全ての要素が条件を満たす場合に備えた初期値
int right = X.size(); // 全ての要素が条件を満たさない場合に備えた初期値
// 両端の差が1になるまで続ける
while (right - left > 1){
int mid = left + (right - left) / 2; // 区間の真ん中
if (is_ok(X[mid], key)) right = mid; // もし調べている対象が「条件」そのものであればindexを返す
else left = mid; // もし調べている対象が「条件」である対象よりも小さければ左端を移動
}
return right;
}
vector<int> X = {1, 3, 5, 7, 9};
int main(){
cout << binary_search(X, 0) << endl; // 0
cout << binary_search(X, 1) << endl; // 0
cout << binary_search(X, 2) << endl; // 1
cout << binary_search(X, 3) << endl; // 1
cout << binary_search(X, 4) << endl; // 2
cout << binary_search(X, 5) << endl; // 2
cout << binary_search(X, 6) << endl; // 3
cout << binary_search(X, 7) << endl; // 3
cout << binary_search(X, 8) << endl; // 4
cout << binary_search(X, 9) << endl; // 4
cout << binary_search(X, 10) << endl; // 5
}しっかりと「領域」の条件に沿うような形で出力されているね。
ポイント
繰り返しますが，大切なことは「ソートされた配列」から「条件を満たす要素を探し出す」という部分です。二分探索では，前提として配列はソート済みとします。
また，条件部分を累積和のアナロジーとして「ピンポイントから領域へ」拡張させることで，より汎用的な二分探索が可能になります。「条件を満たさなければ-1」ではなく，「条件を満たす最小のインデックス」とできる点がキモです。
応用問題
探索の対象は必ずしも配列でなくても構いません。ある範囲にある数を対象としたい場合は，単に左端と右端をスカラーで与えてあげればOKです。以下の記事を参考にしてください。
コメント