この記事は 競プロ Advent Calendar 2023 の 23 日目の記事です。
油断するとすぐに頭がこんがらがるので、整理します。Python 派の人は適宜 bisect_left と bisect_right と読み替えてください。なお、ポインタを使って説明した方が正確ですが、わかりやすさのために、敢えてそこら辺を曖昧にして「インデックス」という説明に統一しています。
lower_boundとupper_bound
基礎：密な数列
違いがわかりづらいこの 2 つですが、わかりやすいのは 密な数列 のインデックスを探す時です。ここでいう密な数列とは、同じ数字が重複している数列のことです。
a = {1,1,2,2,2,3,3}
という数列があったとします。
この時、2 をキーとした場合、lower_bound と upper_bound では以下のようなインデックスを返します。
つまり、lower_bound はギリギリ左の、upper_bound はギリギリ右のインデックスを返します。
コード実例（ビルトイン関数使用）
int main()
{
vector<int> a = {1, 1, 2, 2, 2, 3, 3};
int idx = lower_bound(all(a),2) - a.begin();
cout << idx << endl; // 2
}
int main()
{
vector<int> a = {1, 1, 2, 2, 2, 3, 3};
int idx = upper_bound(all(a),2) - a.begin();
cout << idx << endl; // 5
}
これはそれぞれ以下のような二分探索と同じです。
コード実例（フルスクラッチ実装）
int main()
{
vector<int> a = {1, 1, 2, 2, 2, 3, 3};
int ng = 0;
int ok = 7;
while (abs(ng - ok) > 1)
{
int mid = ng + ok;
mid /= 2;
if (a[mid] >= 2) // 以上
{
ok = mid;
}
else
{
ng = mid;
}
}
cout << ok << endl; // 2
}
int main()
{
vector<int> a = {1, 1, 2, 2, 2, 3, 3};
int ng = 0;
int ok = 7;
while (abs(ng - ok) > 1)
{
int mid = ng + ok;
mid /= 2;
if (a[mid] > 2) // 超過
{
ok = mid;
}
else
{
ng = mid;
}
}
cout << ok << endl; // 5
}
応用：疎な数列
では、疎な数列 の時はどうでしょう。ここでいう疎な数列とは、重複しない、かつ、離れた数字が出てくる数列のことです。このような時は、「$x$ 以上の最小の要素」とか「$x$ 以下の最大の整数」という形で違いが出てきます。
a = {1,5,9}
という数列があったとします。
x 以上で最小
この数列の中で、「$x$ 以上で最小の要素」を出したいとします。これは lower_bound で求められます。
コード実例（ビルトイン関数使用）
int main()
{
vector<int> a = {1, 5, 9};
for (int x = 0; x <= 10; x++)
{
int idx = lower_bound(all(a), x) - a.begin();
cout << x << ',';
if(idx < 3){
cout << a[idx] << endl;
}else{
cout << "none" << endl;
}
}
}
0,1
1,1
2,5
3,5
4,5
5,5
6,9
7,9
8,9
9,9
10,none
フルスクラッチで二分探索を実装すると以下のようになります。
コード実例（フルスクラッチ実装）
int main()
{
vector<int> a = {1, 5, 9};
for (int x = 0; x <= 10; x++)
{
int ng = -1;
int ok = 3;
while (abs(ng - ok) > 1)
{
int mid = ng + ok;
mid /= 2;
if (a[mid] >= x) // 以上
{
ok = mid;
}
else
{
ng = mid;
}
}
cout << x << ',';
if (ok < 3)
{
cout << a[ok] << endl;
}
else
{
cout << "none" << endl;
}
}
}
x 以下で最大
慣れていないと面食らうのが、「$x$ 以下の最大の整数」を求める時です。これは、結論から言うと、「upper_bound で求めたインデックスから 1 を引く」というワンクッションが必要になります。
コード実例（ビルトイン関数使用）
int main()
{
vector<int> a = {1, 5, 9};
for (int x = 0; x <= 10; x++)
{
int idx = upper_bound(all(a), x) - a.begin();
cout << x << ',';
if(idx > 0){
cout << a[idx-1] << endl; // 1 を引く
}else{
cout << "none" << endl;
}
}
}
0,none
1,1
2,1
3,1
4,1
5,5
6,5
7,5
8,5
9,9
10,9
実は、フルスクラッチで二分探索を実装すれば、このようなワンクッションは要りません。
コード実例（フルスクラッチ実装）
int main()
{
vector<int> a = {1, 5, 9};
for (int x = 0; x <= 10; x++)
{
int ok = -1;
int ng = 3;
while (abs(ng - ok) > 1)
{
int mid = ng + ok;
mid /= 2;
if (a[mid] <= x) // 以下
{
ok = mid;
}
else
{
ng = mid;
}
}
cout << x << ',';
if (ok >= 0) // 0 以上であることに注意
{
cout << a[ok] << endl; // 1 は引かない
}
else
{
cout << "none" << endl;
}
}
}
後者の方が、問題の意図をコードに落とし込むという点ではわかりやすいです。
最小化と最大化の違い
この違いが出てくるのは、前者がやっているのは、ある条件を満たす値の 最小化 であり、後者は 最大化 だからです。最小化では、大きければ大きい程都合が良い値をいかに小さくするか という勝負をしており、最大化では、小さければ小さい程都合が良い値をいかに大きくするか という勝負をしています。（フルスクラッチの実装例では、後者では ok = -1 になっています）
しかし、ビルトインの lower_bound や upper_bound は、「最小化」側のロジックを使っています。なので、「最大化」側のインデックスを求める場合は、「求める条件を満たさない最小のインデックスから 1 を引く」という回り道をする必要があります。
ビジュアライズ
ちなみに、両者の挙動の違いをビジュアライズすると以下のようになります。
upper のインデックスから 1 を引いたものが示す要素が、うまい感じに「$x$ 以下の最大の要素」になっています。
最も近い要素との比較
また、疎な数列で時々テーマになるのが、最も近い要素との比較 です。
a = {4,6,9}
ある $x$ が与えられたときに、この数列の中で最も近い要素との距離を求めたいとします。二分探索で求められるのはなんとなくわかりますが、境界条件はどうすればいいのでしょうか。また、使うのは、lower_bound か upper_bound か？
結論としては、どっちでもいいです。
数列に含まれない要素を比較したときは、どちらでも変わりません。数列に含まれる要素を比較したときの答えは自明に $0$ です。このとき、lower_bound なら余計に左側との差を取り、upper_bound なら余計に右側との差を取りますが、いずれにせよ $0$ になります。
気をつけなければいけないのは、左端や右端を超えたインデックスを取ってしまうことです。if で分岐処理してもいいですが、番兵をつけて処理することもできます。
このようなときに左側の番兵に 0 を置くとバグるので気をつけてください。正しくは、事実上の $-\infty$ となる十分に小さい値です。
コード実例
int main()
{
vector<int> a = {3, 5, 8};
a.push_back(2e9); // 十分大きい値に
a.push_back(-2e9); // 十分小さい値に
sort(all(a));
for (int i = 0; i <= 10; i++)
{
int L_idx = lower_bound(all(a), i) - a.begin();
int L_min = min(a[L_idx] - i, i - a[L_idx - 1]);
int U_idx = upper_bound(all(a), i) - a.begin();
int U_min = min(a[U_idx] - i, i - a[U_idx - 1]);
cout << L_min << ',' << U_min << endl; // 同じになる
}
}
3,3
2,2
1,1
0,0
1,1
0,0
1,1
1,1
0,0
1,1
2,2
発展1：除算の比較
a = {1,5,9,13,...} // 1 + 4*n の形
このような規則的な数列の場合「$x$ 以上の最小の要素」「$x$ 以下の最大の要素」は、わざわざ二分探索を使わなくても、$O(1)$ で求めることができます。これは自明のようですが、この計算を瞬時に、ミスなくできるでしょうか？
まず単純な例として、余計な補正がない以下の数列を考えてみます。
a = {0,4,8,12,...} // 4*n の形
これに対して、単純な繰り上げ除算（ceil）と繰り上げ除算（floor）に対する結果を確かめてみます。
コード実例（繰り上げ）
int main()
{
for (int x = 0; x <= 10; x++)
{
int idx = (x + 3) / 4; // 繰り上げ
cout << x << ',';
cout << idx * 4 << endl;
}
}
0,0
1,4
2,4
3,4
4,4
5,8
6,8
7,8
8,8
9,12
10,12
コード実例（繰り下げ）
int main()
{
for (int x = 0; x <= 10; x++)
{
int idx = x / 4; // 繰り下げ
cout << x << ',';
cout << idx * 4 << endl;
}
}
0,0
1,0
2,0
3,0
4,4
5,4
6,4
7,4
8,8
9,8
10,8
これをビジュアライズすると、面白いことがわかります。
繰り上げの挙動は、lower_bound つまり「$x$ 以上の最小の要素」を求める時の挙動と、繰り下げの挙動は upper_bound - 1 つまり「$x$ 以下の最大の要素」を求める時の挙動と似ていることがわかります。
このことから、
a = {1,5,9,...}
に対しては、
- 起点が $0$ になるように並行移動
- 単純な除算
- 元の位置に戻す
という操作を考えれば、
- 「$x$ 以上の最小の要素」は $\lceil \frac{x-1}{4} \rceil \times 4 + 1 = \lfloor \frac{x+2}{4} \rfloor \times 4 + 1$
- 「$x$ 以下の最大の要素」は $\lfloor \frac{x-1}{4} \rfloor \times 4 + 1$
で求められることがわかります。
コード実例（x 以上の最小）
int main()
{
for (int x = 0; x <= 10; x++)
{
cout << x << ',';
cout << (x + 2) / 4 * 4 + 1 << endl;
}
}
0,1
1,1
2,5
3,5
4,5
5,5
6,9
7,9
8,9
9,9
10,13
コード実例（x 以下の最大）
int main()
{
for (int x = 0; x <= 10; x++)
{
cout << x << ',';
if (x - 1 < 0)
{
cout << "none" << endl;
}
else
{
cout << (x - 1) / 4 * 4 + 1 << endl;
}
}
}
0,none
1,1
2,1
3,1
4,1
5,5
6,5
7,5
8,5
9,9
10,9
発展2：整数と分数の厳密比較
ある整数 $z$ と、ある整数同士の分数 $\frac{p}{q}$ との厳密な比較は以下のように整理されます。
- $z \leq \frac{p}{q} \Longleftrightarrow z \leq \lfloor \frac{p}{q} \rfloor$
- $z \geq \frac{p}{q} \Longleftrightarrow z \geq \lceil \frac{p}{q} \rceil$
- $z < \frac{p}{q} \Longleftrightarrow z < \lceil \frac{p}{q} \rceil \Longleftrightarrow z \leq \lceil \frac{p}{q} \rceil - 1$
- $z > \frac{p}{q} \Longleftrightarrow z > \lfloor \frac{p}{q} \rfloor \Longleftrightarrow z \geq \lfloor \frac{p}{q} \rfloor + 1$
境界条件に絞ると、以下のことが言えます。
- $\frac{p}{q}$ 以下の最大の整数は $\lfloor \frac{p}{q} \rfloor$
- $\frac{p}{q}$ 以上の最小の整数は $\lceil \frac{p}{q} \rceil$
- $\frac{p}{q}$ 未満の最大の整数は $\lceil \frac{p}{q} \rceil - 1$
- $\frac{p}{q}$ より大きい最小の整数は $\lfloor \frac{p}{q} \rfloor + 1$
上の不等式の証明は yamate さんの記事に書かれていますが、このことを別の方面から証明します。
- $\frac{p}{q}$ 以下の最大の整数
これは、$z \cdot q \leq p$ を満たす最大の $z$ と言い換えることもできます。つまり、最大化 をする問題です。なので、「除算の比較」の章で述べたように、繰り下げ除算がその答えになります。
- $\frac{p}{q}$ 以上の最小の整数
これは、$z \cdot q \geq p$ を満たす最小の $z$ と言い換えることもできます。つまり、最小化 をする問題なので、繰り上げ除算がその答えになります。
- $\frac{p}{q}$ 未満の最大の整数
$\frac{p}{q}$ 未満は、$\frac{p}{q}$ 以上の背反条件なので、その答えに $-1$ したものが答えになります。
- $\frac{p}{q}$ より大きい最小の整数
$\frac{p}{q}$ より大きいは、$\frac{p}{q}$ 以下の背反条件なので、その答えに $+1$ したものが答えになります。
upper_bound で求めているものは、まさにこの「より大きい」になります。この $+1$ と、「『以下』を求めるために upper_bound から 1 を引くこと」は、同じ操作を別の方面から述べていることになります。