lower_boundとかupper_boundとか「～を満たす最小」とか「～を満たす最大」とかを徹底的に整理

https://adventar.org/calendars/8745

　この記事は [競プロ Advent Calendar 2023](https://adventar.org/calendars/8745) の 23 日目の記事です。

　油断するとすぐに頭がこんがらがるので、整理します。Python 派の人は適宜 `bisect_left` と `bisect_right` と読み替えてください。なお、ポインタを使って説明した方が正確ですが、わかりやすさのために、敢えてそこら辺を曖昧にして「インデックス」という説明に統一しています。
 
# lower_boundとupper_bound

## 基礎：密な数列

　違いがわかりづらいこの 2 つですが、わかりやすいのは **密な数列** のインデックスを探す時です。ここでいう密な数列とは、同じ数字が重複している数列のことです。

 ```c++
 a = {1,1,2,2,2,3,3}
 ```

 　という数列があったとします。
  
  　この時、`2` をキーとした場合、`lower_bound` と `upper_bound` では以下のようなインデックスを返します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/e233f1a5-e7b5-eedf-7615-021cb6323b7a.png)

　つまり、`lower_bound` は**ギリギリ左**の、`upper_bound` は**ギリギリ右**のインデックスを返します。

<details><summary>コード実例（ビルトイン関数使用）</summary><div>

```c++: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
}
```

```c++: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
}
```

</div></details>

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

<details><summary>コード実例（フルスクラッチ実装）</summary><div>

```c++: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
}
```

```c++: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
}
```

</div></details>

## 応用：疎な数列

　では、**疎な数列** の時はどうでしょう。ここでいう疎な数列とは、重複しない、かつ、離れた数字が出てくる数列のことです。このような時は、「$x$ 以上の最小の要素」とか「$x$ 以下の最大の整数」という形で違いが出てきます。

```c++
a = {1,5,9}
```

　という数列があったとします。

### x 以上で最小
 
 　この数列の中で、「$x$ 以上で最小の要素」を出したいとします。これは `lower_bound` で求められます。

<details><summary>コード実例（ビルトイン関数使用）</summary><div>

```c++: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
```

</div></details>

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

<details><summary>コード実例（フルスクラッチ実装）</summary><div>

```c++: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;
        }
    }
}
```

</div></details>

### x 以下で最大

　慣れていないと面食らうのが、「$x$ 以下の最大の整数」を求める時です。これは、結論から言うと、「`upper_bound` で求めたインデックスから **1 を引く**」というワンクッションが必要になります。

<details><summary>コード実例（ビルトイン関数使用）</summary><div>

 ```c++: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
```

</div></details>

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

<details><summary>コード実例（フルスクラッチ実装）</summary><div>

```c++: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;
        }
    }
}
```

</div></details>

　後者の方が、問題の意図をコードに落とし込むという点ではわかりやすいです。

 ### 最小化と最大化の違い

 　この違いが出てくるのは、前者がやっているのは、ある条件を満たす値の **最小化** であり、後者は **最大化** だからです。最小化では、**大きければ大きい程都合が良い値をいかに小さくするか** という勝負をしており、最大化では、**小さければ小さい程都合が良い値をいかに大きくするか** という勝負をしています。（フルスクラッチの実装例では、後者では `ok = -1` になっています）

  　しかし、ビルトインの `lower_bound` や `upper_bound` は、「最小化」側のロジックを使っています。なので、「最大化」側のインデックスを求める場合は、「求める条件を満たさない最小のインデックスから 1 を引く」という回り道をする必要があります。

   ### ビジュアライズ

　ちなみに、両者の挙動の違いをビジュアライズすると以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/5c8cd03d-1524-5103-f389-aa6067e36a10.png)


　**upper** のインデックスから 1 を引いたものが示す要素が、うまい感じに「$x$ 以下の最大の要素」になっています。

### 最も近い要素との比較

　また、疎な数列で時々テーマになるのが、**最も近い要素との比較** です。

```c++
a = {4,6,9}
```

　ある $x$ が与えられたときに、この数列の中で最も近い要素との距離を求めたいとします。二分探索で求められるのはなんとなくわかりますが、境界条件はどうすればいいのでしょうか。また、使うのは、`lower_bound` か `upper_bound` か？

　結論としては、**どっちでもいい**です。

　数列に含まれない要素を比較したときは、どちらでも変わりません。数列に含まれる要素を比較したときの答えは自明に $0$ です。このとき、`lower_bound` なら余計に左側との差を取り、`upper_bound` なら余計に右側との差を取りますが、いずれにせよ $0$ になります。

 　気をつけなければいけないのは、左端や右端を超えたインデックスを取ってしまうことです。`if` で分岐処理してもいいですが、番兵をつけて処理することもできます。
  
:::note warn
このようなときに左側の番兵に `0` を置くとバグるので気をつけてください。正しくは、事実上の $-\infty$ となる十分に小さい値です。
:::

<details><summary>コード実例</summary>

```c++
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; // 同じになる
    }
}
```

```c++
3,3
2,2
1,1
0,0
1,1
0,0
1,1
1,1
0,0
1,1
2,2
```

</details>

  
 # 発展1：除算の比較

```c++
a = {1,5,9,13,...} // 1 + 4*n の形
```

　このような規則的な数列の場合「$x$ 以上の最小の要素」「$x$ 以下の最大の要素」は、わざわざ二分探索を使わなくても、$O(1)$ で求めることができます。これは自明のようですが、この計算を瞬時に、ミスなくできるでしょうか？

　まず単純な例として、余計な補正がない以下の数列を考えてみます。

 ```c++
a = {0,4,8,12,...} // 4*n の形
```

　これに対して、単純な繰り上げ除算（`ceil`）と繰り上げ除算（`floor`）に対する結果を確かめてみます。

<details><summary>コード実例（繰り上げ）</summary><div>

```c++: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
```
</div></details>

<details><summary>コード実例（繰り下げ）</summary><div>

```c++: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
```

</div></details>

　これをビジュアライズすると、面白いことがわかります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/da059b4f-5f45-d7f0-f7c4-25cb10d21e53.png)


　繰り上げの挙動は、`lower_bound` つまり「$x$ 以上の最小の要素」を求める時の挙動と、繰り下げの挙動は `upper_bound - 1` つまり「$x$ 以下の最大の要素」を求める時の挙動と似ていることがわかります。

 　このことから、

  ```
  a = {1,5,9,...}
  ```

　に対しては、
 
 1. 起点が $0$ になるように並行移動
 1. 単純な除算
 1. 元の位置に戻す

　という操作を考えれば、
 
 - 「$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$

 　で求められることがわかります。

<details><summary>コード実例（x 以上の最小）</summary><div>

 ```c++
 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
```

</div></details>

<details><summary>コード実例（x 以下の最大）</summary><div>

```c++
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
```

</div></details>

# 発展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 さんの[記事](https://yamate11.github.io/blog/posts/2021/02-13-int-inequality-floor/)に書かれていますが、このことを別の方面から証明します。

 - $\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$ したものが答えになります。
 
:::note info
`upper_bound` で求めているものは、まさにこの「より大きい」になります。この $+1$ と、「『以下』を求めるために `upper_bound` から 1 を引くこと」は、同じ操作を別の方面から述べていることになります。
:::