#1.lower_boundとupper_bound
lower_boundとupper_boundはC++のSTLライブラリの関数なのじゃ…
俗に言う二分探索に似たやつなのじゃ…
違いとしては
- lower_boundは、探索したいkey以上のイテレータを返す
- upper_boundは、探索したいkeyより大きいイテレータを返す
という点なのじゃ…
…ただの二分探索と何が違うんじゃという声が聞こえてきたのじゃ…
binary_searchとの違いを比べつつ、それぞれの関数の性質を見ていこうと思うのじゃ…
#2. binary_search
binary_searchは一番シンプルな二分探索じゃの…
ソートされた配列やvectorの中に、keyがあるかどうかを探索するのじゃ…
関数の返り値はbool値であり
- keyがあるかどうかは分かる
- しかし、どこにkeyがあるのか分からない
- さらに、同じ値のkeyが複数あったとき、どのkeyを指しているのか分からない
という特徴があるのじゃ…
lower_boundとupper_boundは、この欠点を補った二分探索というわけじゃな…
ただ、keyがあるかどうかだけを調べたいんじゃったら、binary_searchだけでいいのじゃ…
以下、使用例じゃ…
int main() {
//ソートする必要があるのじゃ…
vector<int> a = { 1,4,4,7,7,8,8,11, 13, 19 };
cout << binary_search(a.begin(), a.end(), 4) << endl; //True
cout << binary_search(a.begin(), a.end(), 9) << endl; //False
cout << binary_search(a.begin(), a.end(), 3) << endl; //False
}
#3.lower_bound
##3-1.lower_boundとは
lower_boundは、ソートされた配列内で、key以上の要素の内の一番左側のイテレータを返すのじゃ･･･
{2, 2, 5, 5, 9}という配列があった時
- $key=2$なら、0番目のイテレータ(2以上のうち2が一番左側のため)
- $key=4$なら、2番目のイテレータ(4以上のうち5が一番左側のため)
- $key=5$なら、2番目のイテレータ(5以上のうち5が一番左側のため)
- $key=7$なら、4番目のイテレータ(7以上のうち9が一番左側のため)
- $key=100$なら、5番目のイテレータ(100以上のものがないため、一番右側となる)
のような動作になるのじゃ･･･
keyを配列に挿入する時、どこに挿入するべきかをイテレータが表しているともとることができるのじゃ･･･
##3-2.ソースコード例
#define ALL(a) (a).begin(),(a).end()
int main() {
//ソートする必要があるのじゃ…
vector<int> a = {1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
//イテレータを返す
auto Iter1 = lower_bound(ALL(a), 4);
auto Iter2 = lower_bound(ALL(a), 6);
auto Iter3 = lower_bound(ALL(a), 7);
auto Iter4 = lower_bound(ALL(a), 19);
auto Iter5 = lower_bound(ALL(a), 20);
//値の表示
cout << "----------value----------" << endl;
cout << "Iter1 = " << *Iter1 << endl; //Iter1 = 4
cout << "Iter2 = " << *Iter2 << endl; //Iter2 = 7
cout << "Iter3 = " << *Iter3 << endl; //Iter3 = 7
cout << "Iter4 = " << *Iter4 << endl; //Iter4 = 19
cout << "Iter5 = " << *Iter5 << endl; //Iter5 = 1326115891
//先頭からの距離
cout << "----------from----------" << endl;
cout << "Iter1 = " << Iter1 - a.begin() << endl; //Iter1 = 1
cout << "Iter2 = " << Iter2 - a.begin() << endl; //Iter2 = 3
cout << "Iter3 = " << Iter3 - a.begin() << endl; //Iter3 = 3
cout << "Iter4 = " << Iter4 - a.begin() << endl; //Iter4 = 9
cout << "Iter5 = " << Iter5 - a.begin() << endl; //Iter5 = 10
//末尾までの距離
cout << "----------to----------" << endl;
cout << "Iter1 = " << a.end() - Iter1 << endl; //Iter1 = 9
cout << "Iter2 = " << a.end() - Iter2 << endl; //Iter2 = 7
cout << "Iter3 = " << a.end() - Iter3 << endl; //Iter3 = 7
cout << "Iter4 = " << a.end() - Iter4 << endl; //Iter4 = 1
cout << "Iter5 = " << a.end() - Iter5 << endl; //Iter5 = 0
return 0;
}
##3-3.性質
lower_boundを利用する利点としては、やはり、binary_searchよりも得られる情報が多いということがあるのじゃ･･･
ソースコードとにらめっこしてもらうと分かるのじゃが、以下のような性質があるのじゃ･･･
- lower_boundのイテレータから先頭のイテレータを引くと、あるkeyより小さい要素の個数を求めることができる。
- 末尾のイテレータからlower_boundのイテレータを引くと、あるkey以上の要素の個数を求めることができる。
･･･よく分からんと思うので、ソースコードを改めて見てみようとおもうのじゃ･･･
//ソートする必要があるのじゃ…
vector<int> a = {1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
//イテレータを返す
auto Iter1 = lower_bound(ALL(a), 4);
auto Iter2 = lower_bound(ALL(a), 6);
auto Iter3 = lower_bound(ALL(a), 7);
auto Iter4 = lower_bound(ALL(a), 19);
auto Iter5 = lower_bound(ALL(a), 20);
//先頭からの距離
cout << "----------from----------" << endl;
cout << "Iter1 = " << Iter1 - a.begin() << endl; //Iter1 = 1
cout << "Iter2 = " << Iter2 - a.begin() << endl; //Iter2 = 3
cout << "Iter3 = " << Iter3 - a.begin() << endl; //Iter3 = 3
cout << "Iter4 = " << Iter4 - a.begin() << endl; //Iter4 = 9
cout << "Iter5 = " << Iter5 - a.begin() << endl; //Iter5 = 10
//末尾までの距離
cout << "----------to----------" << endl;
cout << "Iter1 = " << a.end() - Iter1 << endl; //Iter1 = 9
cout << "Iter2 = " << a.end() - Iter2 << endl; //Iter2 = 7
cout << "Iter3 = " << a.end() - Iter3 << endl; //Iter3 = 7
cout << "Iter4 = " << a.end() - Iter4 << endl; //Iter4 = 1
cout << "Iter5 = " << a.end() - Iter5 << endl; //Iter5 = 0
例えば、7をkeyとすると、先頭からの距離の値は3となっているのじゃ･･･7より小さい数が3個存在しているというわけじゃな･･･
また、7をkeyとすると、末尾までの距離の値は7となっているのじゃ･･･7以上の数が7個存在しているというわけじゃな･･･
こんなふうに、lower_boundには色々な性質があるわけじゃな･･･多分もっと色々な性質があって、妾には理解できていないのじゃ･･･コメントで教えていただけるとありがたいのじゃ･･･
#4.upper_bound
##4-1.upper_boundとは
upper_boundは、ソートされた配列内で、keyより大きい要素の内の一番左側のイテレータを返すのじゃ･･･
{2, 2, 5, 5, 9}という配列があった時
- $key=2$なら、2番目のイテレータ(2より大きいうち5が一番左側のため)
- $key=4$なら、2番目のイテレータ(4より大きいうち5が一番左側のため)
- $key=5$なら、4番目のイテレータ(5より大きいうち9が一番左側のため)
- $key=7$なら、4番目のイテレータ(7より大きいうち9が一番左側のため)
- $key=100$なら、5番目のイテレータ(100より大きいものがないため、一番右側となる)
のような動作になるのじゃ･･･
keyを配列に挿入する時、配列の単調増加を崩さないように、できるだけ後方に挿入する箇所をイテレータが表しているともとることができるのじゃ･･･
##4-2.ソースコード例
#define ALL(a) (a).begin(),(a).end()
int main() {
//ソートする必要があるのじゃ…
vector<int> a = {1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
//イテレータを返す
auto Iter1 = upper_bound(ALL(a), 4);
auto Iter2 = upper_bound(ALL(a), 6);
auto Iter3 = upper_bound(ALL(a), 7);
auto Iter4 = upper_bound(ALL(a), 19);
auto Iter5 = upper_bound(ALL(a), 20);
//値の表示
cout << "----------value----------" << endl;
cout << "Iter1 = " << *Iter1 << endl; //Iter1 = 7
cout << "Iter2 = " << *Iter2 << endl; //Iter2 = 7
cout << "Iter3 = " << *Iter3 << endl; //Iter3 = 8
cout << "Iter4 = " << *Iter4 << endl; //Iter4 = 1326115891
cout << "Iter5 = " << *Iter5 << endl; //Iter5 = 1326115891
//先頭からの距離
cout << "----------from----------" << endl;
cout << "Iter1 = " << Iter1 - a.begin() << endl; //Iter1 = 3
cout << "Iter2 = " << Iter2 - a.begin() << endl; //Iter2 = 3
cout << "Iter3 = " << Iter3 - a.begin() << endl; //Iter3 = 5
cout << "Iter4 = " << Iter4 - a.begin() << endl; //Iter4 = 10
cout << "Iter5 = " << Iter5 - a.begin() << endl; //Iter5 = 10
//末尾までの距離
cout << "----------to----------" << endl;
cout << "Iter1 = " << a.end() - Iter1 << endl; //Iter1 = 7
cout << "Iter2 = " << a.end() - Iter2 << endl; //Iter2 = 7
cout << "Iter3 = " << a.end() - Iter3 << endl; //Iter3 = 5
cout << "Iter4 = " << a.end() - Iter4 << endl; //Iter4 = 0
cout << "Iter5 = " << a.end() - Iter5 << endl; //Iter5 = 0
return 0;
}
4-3.性質
upper_boundを利用する理由もやはり、binary_searchよりも得られる情報が多いからなのじゃ･･･
例えば、以下のような性質があるのじゃ･･･
- upper_boundのイテレータから先頭のイテレータを引くと、あるkey以下の要素の個数を求めることができる。
- 末尾のイテレータからupper_boundのイテレータを引くと、あるkeyより大きい要素の個数を求めることができる。
ソースコードをじっと見てみたり、コーディングしてみると見えてくるとおもうのじゃ･･･
#define ALL(a) (a).begin(),(a).end()
int main() {
//ソートする必要があるのじゃ…
vector<int> a = {1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
//イテレータを返す
auto Iter1 = upper_bound(ALL(a), 4);
auto Iter2 = upper_bound(ALL(a), 6);
auto Iter3 = upper_bound(ALL(a), 7);
auto Iter4 = upper_bound(ALL(a), 19);
auto Iter5 = upper_bound(ALL(a), 20);
//先頭からの距離
cout << "----------from----------" << endl;
cout << "Iter1 = " << Iter1 - a.begin() << endl; //Iter1 = 3
cout << "Iter2 = " << Iter2 - a.begin() << endl; //Iter2 = 3
cout << "Iter3 = " << Iter3 - a.begin() << endl; //Iter3 = 5
cout << "Iter4 = " << Iter4 - a.begin() << endl; //Iter4 = 10
cout << "Iter5 = " << Iter5 - a.begin() << endl; //Iter5 = 10
//末尾までの距離
cout << "----------to----------" << endl;
cout << "Iter1 = " << a.end() - Iter1 << endl; //Iter1 = 7
cout << "Iter2 = " << a.end() - Iter2 << endl; //Iter2 = 7
cout << "Iter3 = " << a.end() - Iter3 << endl; //Iter3 = 5
cout << "Iter4 = " << a.end() - Iter4 << endl; //Iter4 = 0
cout << "Iter5 = " << a.end() - Iter5 << endl; //Iter5 = 0
return 0;
}
#5.lower_boundとupper_boundの組み合わせ
実は、lower_boundとupper_boundに同じkeyを指定して、イテレータの差をとると、keyの値の要素の個数となるのじゃ･･･
じっくり考えるとわかるんじゃが
- lower_boundはkey以上の中でできるだけ左側
- upper_boundはkeyより大きいなかでできるだけ左側
であり、個数を求めることになるのじゃ･･･
以下のソースコードを見ると分かると思うのじゃ･･･
#define ALL(a) (a).begin(),(a).end()
int main() {
//ソートする必要があるのじゃ…
vector<int> a = {1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
//イテレータを返す
auto low1 = lower_bound(ALL(a), 4);
auto up1 = upper_bound(ALL(a), 4);
auto low2 = lower_bound(ALL(a), 5);
auto up2 = upper_bound(ALL(a), 5);
auto low3 = lower_bound(ALL(a), 11);
auto up3 = upper_bound(ALL(a), 11);
cout << "up1 - low1 = " << up1 - low1 << endl; //up1 - low1 = 2
cout << "up2 - low2 = " << up2 - low2 << endl; //up2 - low2 = 0
cout << "up3 - low3 = " << up3 - low3 << endl; //up3 - low3 = 1
return 0;
}
#6.二分探索とは
これまで、lower_boundとupper_boundについてみてきたのじゃ･･･
実は、二分探索は数値の大小には限らず、実はもっと概念的な存在らしいのじゃ･･･
以下のようなものじゃ･･･
- あるルールに従って並べられた要素を考える。
- ある条件を満たす左側の要素を真とする。
- ある条件を満たさない右側の要素を、偽とする。
二分探索は、この真と偽の境界を探すことに等しいのじゃ･･･
先程までの、数列の大小も、keyより大きいか小さいかの境界を探していたのじゃ･･･
lower_bound,upper_bound関数には、自作比較関数ポインタを渡すことができ、その比較関数に従って、境界を探すことができるらしいのじゃ･･･
妾もまた、ここらへんのめぐる式二分探索が理解できていないのじゃ･･･
参考文献のサイトが非常にわかりやすいのでそちらを要チェックなのじゃ!
#7.参考文献