求比 k 大的最小值 lower_bound/upper_bound

lower_bound() 與 upper_bound() 能在指定的範圍中，找到比給定值

k

大的第一個（也就是範圍中最左邊的）元素，回傳其 iterator。

應用例

以下示範如何用 upper_bound() 找到比指定值

k

大的第一個元素。


#include <algorithm>



int n, k;
int ary[N];
vector<int> v;

陣列版本：
















// 先 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> 版本：

















// 先 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} \geq k$ 且對範圍內任何
$j < i$ 滿足
$A_{j} < k$
upper_bound() 對指定範圍尋找最小的
$i$ 使得
$A_{i} > k$ 且對範圍內任何
$j < i$ 滿足
$A_{j} \leq k$

實作原理

實作上使用 binary search，因此前提為

對詢問值
$k$ 滿足可 bi-partitioned（後述）
指定範圍支援 random access

指定範圍包含

N

個元素時，複雜度為

O (\log N)

。

注意：儘管對不支援 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} \leq k$
對所有
$j \geq i$ 滿足
$A_{j} > k$

則說此範圍對詢問值

k

滿足 bi-partitioned 的條件。此時定義函數

f

如下

對所有
$A_{i} \leq 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

個參數指定，如下：


auto it = upper_bound(ary, ary+n, k, comp);

compare function comp(a, b) 必須使詢問值

k

在搜尋範圍內滿足存在一個

i

使得

對所有
$j < i$ 滿足
$comp (k, A_{j}) = 0$ （表示
$k < A_{j}$ 不成立，意味著
$k \geq A_{j}$ ）
對所有
$j \geq i$ 滿足
$comp (k, A_{j}) = 1$ （表示
$k < A_{j}$ 成立）

設函數

f (i) = comp (k, A_{i})

則

f

具單調性，可以 binary search 找到分界點。

注意 compare 的坑

從上式可以想到，由於比較時是將詢問值

k

拿來和搜尋範圍內的值放進 compare function 比較，所以可能導致一些問題，以下用查表的例子：




bool comp(const int &a, const int &b)
{
    return tbl[a] < tbl[b];
}

搜尋時很直觀地會想這樣寫：


auto it = upper_bound(ary, ary+n, k, comp);

然後就出事了。為什麼？

這是因為我們想搜的是

f (i) = t b l [A_{i}] > k

，但比較時是使用 comp(a, b) 所以

k

也會被對等地拿去查表，邏輯變成比較

f (i) = t b l [A_{i}] > t b l [k]

所以會發生問題。

解決方法是使用任何方式生出一個

t

使得

t b l [t] = k

然後改成搜尋

t

即可。以下是一種例子，但不限於此方法：


tbl[n] = k;
auto it = upper_bound(ary, ary+n, n, comp);

如此一來，搜的便是

f (i) = t b l [A_{i}] > t b l [n] = k

了。

小結

lower_bound() 和 upper_bound() 雖可在部份情境用來做 binary search 無須自行實作，不過並不能完全取代 binary search。

原因是它強制了

f (i) = A_{i}

這樣的形式，使得搜尋的定義域不限於整數、或者大到無法以 container 儲存（對定義域全部計算一遍也不划算而且沒有必要）等情況，仍然必須自行實作 binary search。

回傳的形式相對不好處理，可能的坑也不少，需要特別小心地去熟悉它。

歡樂練習時間

AtCoder abc212_c - Min Difference

https://atcoder.jp/contests/abc212/tasks/abc212_c