# 求比 k 大的最小值 lower_bound/upper_bound
`lower_bound()` 與 `upper_bound()` 能在指定的範圍中，找到比給定值 $k$ 大的第一個（也就是範圍中最左邊的）元素，回傳其 iterator。
## 應用例
以下示範如何用 `upper_bound()` 找到比指定值 $k$ 大的第一個元素。
```cpp=
#include <algorithm>
```
```cpp=
int n, k;
int ary[N];
vector<int> v;
```
陣列版本：
```cpp=
// 先 sort 以滿足使用前提
sort(ary, ary+n);
// 回傳會是位置，對陣列而言是 pointer
// 範圍左包含、右不包含，k 是詢問值，upper_bound 回傳比 k 大的第一個元素
auto it = upper_bound(ary, ary+n, k);
// 回傳的位置為指定範圍最右側（即不包含的位置）時表示找不到
if (it == ary+n)
{
cout << "no element larger than " << k << ".\n";
}
// pointer 透過取值運算子 * 可拿到該位置所儲存的值
// poinetr 相減可得到位置差（距離），和初始位置 ary 相減的值等同於 index
else
{
cout << "ary[" << (it-ary) << "] = " << *it << " found.\n";
}
```
`vector<T>` 版本：
```cpp=
// 先 sort 以滿足使用前提
sort(v.begin(), v.end());
// 回傳會是位置，對 vector 而言是 iterator
// 範圍左包含、右不包含，k 是詢問值，upper_bound 回傳比 k 大的第一個元素
auto it = upper_bound(v.begin(), v.end(), k);
// 回傳的位置為指定範圍最右側（即不包含的位置）時表示找不到
if (it == v.end())
{
cout << "no element larger than " << k << ".\n";
}
// iterator 透過取值運算子 * 可拿到其指稱元素的值
// 支援 random access 的 container 其 iterator 可透過相減得到位置差（距離）
// 和初始位置 v.begin() 相減時等同於 index
else
{
cout << "v[" << (it-v.begin()) << "] = " << *it << " found.\n";
}
```
`lower_bound()` 的用法和 `upper_bound()` 完全相同，差異在找到的值會是不比 $k$ 小的第一個元素。也就是說，
- `lower_bound()` 對指定範圍尋找最小的 $i$ 使得 $A_i\ge k$ 且對範圍內任何 $j<i$ 滿足 $A_j<k$
- `upper_bound()` 對指定範圍尋找最小的 $i$ 使得 $A_i > k$ 且對範圍內任何 $j<i$ 滿足 $A_j\le k$
## 實作原理
實作上使用 binary search，因此前提為
- 對詢問值 $k$ 滿足可 bi-partitioned（後述）
- 指定範圍支援 random access
指定範圍包含 $N$ 個元素時，複雜度為 $O(\log N)$。
:::danger
注意：儘管**對不支援 random access 的 iterator 也能使用**，但此時無法 binary search（因為無法 $O(1)$ 拜訪中間元素）所以**複雜度會劣化為 $O(N)$**。
:::
### bi-partitioned v.s. 單調性
前面 binary search 的章節說使用前提是搜尋範圍具備單調性，而對於詢問值 $k$ 若滿足 bi-partitioned 的性質，就可以滿足單調性。以 `upper_bound()` 為例，如果存在一個值 $i$ 使得範圍內
- 對所有 $j<i$ 滿足 $A_j\le k$
- 對所有 $j\ge i$ 滿足 $A_j>k$
則說此範圍對詢問值 $k$ 滿足 bi-partitioned 的條件。此時定義函數 $f$ 如下
- 對所有 $A_i\le k$ 定義函數值 $f(i)=0$
- 對所有 $A_i>k$ 定義函數值 $f(i)=1$
則此函數 $f$ 具單調性，可透過 binary search 找出分界點 $i$，且 $i$ 即為 `upper_bound()` 所求。
## 自定 compare
若今天搜尋範圍雖具備單調性或者可以 bi-partition，但不是以預設的 `operator<` 由小到大的形式，例如可能是由大到小，或者像字串依長度排序等形式，就必須自行指定 compare。
換句話說，當今天 $f(i)=A_i$ 本身不具備單調性，但存在一個 $g$ 使得 $f(i)=g(A_i)$ 具單調性時，只要指定 compare function 的話，`upper_bound()` 仍然可以運作。使用和 sort 時相同的 compare function 即可。
compare function 可透過第 $4$ 個參數指定，如下：
```cpp=
auto it = upper_bound(ary, ary+n, k, comp);
```
compare function `comp(a, b)` 必須使詢問值 $k$ 在搜尋範圍內滿足存在一個 $i$ 使得
- 對所有 $j<i$ 滿足 $\operatorname{comp}(k,A_j)=0$（表示 $k<A_j$ 不成立，意味著 $k\ge A_j$）
- 對所有 $j\ge i$ 滿足 $\operatorname{comp}(k,A_j)=1$（表示 $k<A_j$ 成立）
設函數 $f(i)=\operatorname{comp}(k,A_i)$ 則 $f$ 具單調性，可以 binary search 找到分界點。
### 注意 compare 的坑
從上式可以想到，由於比較時是將詢問值 $k$ 拿來和搜尋範圍內的值放進 compare function 比較，所以可能導致一些問題，以下用查表的例子：
```cpp=
bool comp(const int &a, const int &b)
{
return tbl[a] < tbl[b];
}
```
搜尋時很直觀地會想這樣寫：
```cpp=
auto it = upper_bound(ary, ary+n, k, comp);
```
然後就出事了。為什麼？
這是因為我們想搜的是 $f(i) = tbl[A_i] > k$，但比較時是使用 `comp(a, b)` 所以 $k$ 也會被對等地拿去查表，邏輯變成比較 $f(i) = tbl[A_i] > tbl[k]$ 所以會發生問題。
解決方法是使用任何方式生出一個 $t$ 使得 $tbl[t]=k$ 然後改成搜尋 $t$ 即可。以下是一種例子，但不限於此方法：
```cpp=
tbl[n] = k;
auto it = upper_bound(ary, ary+n, n, comp);
```
如此一來，搜的便是 $f(i) = tbl[A_i] > tbl[n] = k$ 了。
## 小結
`lower_bound()` 和 `upper_bound()` 雖可在部份情境用來做 binary search 無須自行實作，不過並不能完全取代 binary search。
原因是它強制了 $f(i) = A_i$ 這樣的形式，使得搜尋的定義域不限於整數、或者大到無法以 container 儲存（對定義域全部計算一遍也不划算而且沒有必要）等情況，仍然必須自行實作 binary search。
回傳的形式相對不好處理，可能的坑也不少，需要特別小心地去熟悉它。
## 歡樂練習時間
:::success
### AtCoder abc212_c - Min Difference
https://atcoder.jp/contests/abc212/tasks/abc212_c
:::
{%hackmd @sa072686/__style %}
###### tags: `競程：三章`, `競程`
Sign in with Wallet
Connect another wallet