　この記事は競プロ 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 はギリギリ右のインデックスを返します。

コード実例（ビルトイン関数使用）

lower

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
}

upper

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
}

　これはそれぞれ以下のような二分探索と同じです。

コード実例（フルスクラッチ実装）

lower

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
}

upper

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 で求められます。

コード実例（ビルトイン関数使用）

lower

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;
        }
    }
}

output

0,1
1,1
2,5
3,5
4,5
5,5
6,9
7,9
8,9
9,9
10,none

　フルスクラッチで二分探索を実装すると以下のようになります。

コード実例（フルスクラッチ実装）

lower

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 を引く」というワンクッションが必要になります。

コード実例（ビルトイン関数使用）

upper

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;
       }
   }
}

output

0,none
1,1
2,1
3,1
4,1
5,5
6,5
7,5
8,5
9,9
10,9

　実は、フルスクラッチで二分探索を実装すれば、このようなワンクッションは要りません。

コード実例（フルスクラッチ実装）

full scratch

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）に対する結果を確かめてみます。

コード実例（繰り上げ）

ceil

int main()
{
    for (int x = 0; x <= 10; x++)
    {
        int idx = (x + 3) / 4; // 繰り上げ
        cout << x << ',';
        cout << idx * 4 << endl;
    }
}

output

0,0
1,4
2,4
3,4
4,4
5,8
6,8
7,8
8,8
9,12
10,12

コード実例（繰り下げ）

floor

int main()
{
    for (int x = 0; x <= 10; x++)
    {
        int idx = x / 4; // 繰り下げ
        cout << x << ',';
        cout << idx * 4 << endl;
    }
}

output

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;
   }
}

output

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;
        }
    }
}

output

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 を引くこと」は、同じ操作を別の方面から述べていることになります。