---
tags: 成大高階競技程式設計 2021
---
# 2021 Week4 - Search
寫程式時，我們時常會需要在一個陣列中找出某個元素的位置，
而根據不同的條件，可以用不同的演算法來加快尋找的速度，
下面都有給出適用的情境，記得先確認目前的情況是否符合。
> 為了方便起見，下文中的 $N$ 都一律代表被搜尋的陣列的長度，
> $a_i$ 代表陣列中的索引值為 $i$ 的元素（注意 $i$ 是從 $0$ 開始）。
## 線性搜尋法（Linear Search）
### 適用情境
:::success
所有情境
:::
最通用的搜尋方法。
### 實作概念
從陣列的開頭將每個元素一個一個確認，如果發現目標值就回傳其索引值。
時間複雜度：$O(N)$
### 參考實作
```cpp!
/**
* 搜尋 a 中第一個 x 的索引值，若不存在則回傳 -1。
*/
int linear_search(const vector<int>& a, int x) {
int N{a.size()};
for (int i = 0; i < N; ++i)
if (a[i] == x)
return i;
return -1;
}
```
---
## 二分搜尋法（Binary Search）
### [單調性](https://zh.wikipedia.org/wiki/%E5%8D%95%E8%B0%83%E5%87%BD%E6%95%B0#%E4%B8%80%E8%88%AC%E5%AE%9A%E4%B9%89)
在講二分搜之前，我們要先來提一下單調性這個性質。
所謂的單調性，就是可以找到一個函數 $f$，使得當 $i \leq j$ 成立時，$f(i) \leq f(j)$ 也成立。
例如將函數訂為 $f(i) = \begin{cases} 1,&\text{if}\ a_i\geq7\\
0,&\text{otherwise}\end{cases}$，所以陣列 $[-1, 0, 1, 4, 7, 9, 10]$ 透過此函數映射之後會得到 $[0, 0, 0, 0, 1, 1, 1]$，可以看到映射後的陣列有符合單調性的定義。
### 適用情境
:::success
具有單調性的數列。
:::
以 `lower_bound()` 的概念作舉例，此函式是可以找到第一個不小於 $x$ 元素的的索引值，
而它就是將函數訂為 $f(i) = \begin{cases} 1,&\text{if}\ a_i \geq x\\
0,&\text{otherwise}\end{cases}$ 來進行二分搜尋。
> 最常見的用法是在**遞增**或**遞減**數列。
### 實作概念
定義兩個變數 $l$ 和 $r$，將陣列分成三個部分：
1. $[0, l]$：$f(i) = 0$
2. $(l, r)$：尚未確定
3. $[r, N)$：$f(i) = 1$
> 務必看清楚區間是開還是閉。
我們最後的目標就是讓所有元素都是確定的，也就是要讓第 $2$ 部分成為空區間，
而此時的 $l$ 是最後一個使函數回傳 $0$ 的索引，而 $r$ 是第一個使函數回傳 $1$ 的索引。
> 要讓第 $2$ 部分變成空區間，也就是要讓 $r - l \leq 1$ 成立，而我們該如何快速做到這件事？
首先我們會找到 $(l, r)$ 中間的那個元素（令其索引值為 $mid$），接下來會遇到兩種情況：
1. $f(mid) = 0$
2. $f(mid) = 1$
若是第 $1$ 種情況，根據陣列的特性，我們可以知道所有 $(l, mid]$ 中的索引值代入函數後，得到的也會是 $0$，因此可以將此部分合併到第 $1$ 部分，且剩下的未知的部分為 $(mid, r)$，
所以就是將 $l$ 更新為 $mid$，而第 $2$ 種情況也與第 $1$ 種相似，要將 $r$ 更新為 $mid$。
可以看到每次 $l, r$ 的距離都會縮減為原來的一半（也可以看成每次第 $2$ 部分都會減少一半的元素），
因此最多只要 $\lceil \log_2(r - l) \rceil$ 次操作就可以達成目標。
時間複雜度：$O(\log_2(r - l)) = O(\log{N})$
### 參考實作
下面就試著實作 `lower_bound()`，注意回傳的是整數而不是迭代器。
```cpp!
/* f(i) = a[i] >= x ? 1 : 0 */
int my_lower_bound(const vector<int>& a, int x) {
// 一開始所有元素都未確定，因此全部放到第 2 部分
int l{-1}, r{a.size()};
while (r - l > 1) {
int mid{(l + r) / 2};
if (a[mid] >= x) r = mid; // f(mid) = 1
else l = mid;
}
return r;
}
```
> 注意以上程式碼會在少數情況出錯，原因在於 $l$ 和 $r$ 的型別都是 `int`，
> 因此兩數做加法時有可能會遇到整數溢位（integer overflow）的問題，
> 實作時如果遇到上述情況，$mid$ 的算法可改成 $l + \frac{r - l}{2}$。
>
> 但是這個問題不容易遇到，因此通常都還是用 ${l + r} \over 2$ 的寫法，
> 不僅寫起來速度較快，也更容易閱讀。
### 圖解
在 $[-1, 0, 1, 4, 7, 9, 10]$ 中搜尋第一個不小於 $7$ 的元素的索引值，訂 $f(i) = \begin{cases} 1,&\text{if}\ a_i\geq 7\\
0,&\text{otherwise}\end{cases}$。
```graphviz
digraph {
l, r, mid [shape = none]
array [label = "<-1>X|<0>-1|<1>0|<2>1|<3>4|<4>7|<5>9|<6>10|<7>X", shape = record]
l -> array: -1
mid -> array: 3
r -> array: 7
}
```
```graphviz
digraph {
l, r, mid [shape = none]
array [label = "<-1>X|<0>-1|<1>0|<2>1|<3>4|<4>7|<5>9|<6>10|<7>X", shape = record]
l -> array: 3
mid -> array: 5
r -> array: 7
}
```
```graphviz
digraph {
l, r, mid [shape = none]
array [label = "<-1>X|<0>-1|<1>0|<2>1|<3>4|<4>7|<5>9|<6>10|<7>X", shape = record]
l -> array: 3
mid -> array: 4
r -> array: 5
}
```
```graphviz
digraph {
l, r [shape = none]
array [label = "<-1>X|<0>-1|<1>0|<2>1|<3>4|<4>7|<5>9|<6>10|<7>X", shape = record]
l -> array: 3
r -> array: 4
}
```
最後 $r$ 就是我們要找的索引值。
---
### 例題
#### [最長遞增子序列（LIS, Longest Increasing Subsequence）](https://leetcode.com/problems/longest-increasing-subsequence/)
想必各位都對這題有印象，因為這題也有在[第三週教材](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-WayOfThinking)中作為例題出現。
至於這週又出現的原因是原本的 $O(N^2)$ 還不夠快，我們可以用二分搜來做這個題目，並且時間複雜度只有 $O(N \log{N})$！
首先我們需要一個陣列 $last$，定義 $last_i$ 為到目前為止所有長度為 $i$ 的遞增子序列的最後一項的最小值。
> 因為值越小後面就越容易接上其他數字，因此取最小值。
我們可以發現一個元素 $a_i$ 只要大於 $last_j$，他就可以接在後面形成長度為 $j + 1$ 的遞增子序列，且最後一個元素為 $a_i$。
用公式表示就是 $last_{j + 1} = \min(last_{j + 1}, a_i) \iff a_i > last_j$
馬上就可以寫出以下程式碼來解題，
```cpp!
/* 求 a 中 LIS 的長度 */
int LIS(const vector<int>& a) {
// 注意這邊用的是 list-initialization
// 不熟的可以回去翻第二週教材的 vector 部分來複習
vector<int> last{numer_limits<int>::min()};
for (auto ai : a) {
for (size_t j = 1; j < last.size(); ++j)
if (ai > last[j - 1]) last[j] = min(last[j], ai);
if (last.back() < ai) last.push_back(ai);
}
return last.size() - 1;
}
```
但是看起來最壞情況的時間複雜度還是 $O(N^2)$，而且沒有用到二分搜，
那我們再來多觀察一下 $last$ 這個陣列。
可以發現到因為 $last_{i + 1}$ 一定是從 $last_i$ 更新而來，因此可以確定 $last_{i + 1}$ 一定大於 $last_i$，
從這個規律我們可以發現一件事實：==$last$ 為嚴格遞增數列==
因為是嚴格遞增數列，所以我們可以在 $last$ 上面做二分搜，但是要搜什麼？
要搜尋的是「第一個不小於 $a_i$ 的元素」。
假設搜尋到的索引值是 $idx$，可以發現除了 $last_{idx}$ 以外的所有元素都不可能會被更新。
* $last_{idx + 1}$ 不會被更新，因為 $last_{idx} \nless a_i$，後面以此類推。
* $last_{idx - 1}$ 不會被更新，因為 $\min(last_{idx - 1}, a_i) = last_{idx - 1}$，前面以此類推。
因此最終我們可以寫出以下程式碼，
```cpp!
/* 求 a 中 LIS 的長度 */
int LIS(const vector<int>& a) {
vector<int> last{};
for (auto ai : a) {
auto it{lower_bound(last.begin(), last.end(), ai)};
if (it == last.end()) last.push_back(ai);
else *it = ai;
}
return last.size();
}
```
注意到上面的程式碼除了將 `for` 迴圈優化成 `lower_bound()` 外，也將初始的 $last_0$ 也刪除掉了。
理論上，$last_0$ 應該要是任何小於 $a$ 中所有元素的值，
但在實作上，我選擇將他省略。
也就是說，$last_i$ 代表的是到目前為止所有長度為 $i + 1$ 的遞增子序列的最後一項的最小值。
這麼做的原因有以下幾點：
1. 可以少使用一個 `int` 的空間
2. $last_0$（理論上的）永遠不該被更新，因此可以看成是無用的值，且刪掉後對實作也沒有影響
3. 有可能會造成錯誤（這也是最主要的原因）
若是 $a$ 中有 `int` 可以表示的最小值，則因為 $last$ 的元素型別也是 `int`，
所以無法找到一個合適的 $last_0$ 使得「$last_0$ 應該要是任何小於 $a$ 中所有元素的值」這個條件成立
時間複雜度：$O(N \log{N})$
---
#### [c575: APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575)
:::info
一個數線上有 $N$ 個服務點，我們要在數線上設置 $k$ 個基地台。
基地台可以覆蓋以其為中心的直徑為 $d$ 的範圍。
問 $d$ 最小可以設為多少，使得所有服務點有被覆蓋到。
:::
這題的解題關鍵為==在答案上二分搜==。
假設 $x$ 為可以覆蓋所有服務點的最小直徑，我們可以發現所有直徑 $d < x$ 一定無法覆蓋所有的服務點，且所有直徑 $d \geq x$ 一定都有辦法，因此如果我們有辦法得知某個直徑 $d$ 是否可以覆蓋所有的服務點，我們就可以做二分搜。
我們定義函數 $f(d) = 1$ 代表直徑 $d$ 可以覆蓋所有的服務點，$f(d) = 0$ 則代表不行。
假設 $P$ 是已經排序完的服務點座標，則有一個很簡單的方法可以知道 $f(d)$ 的結果。
定義一個變數 $right$ 代表目前已經被覆蓋的最右端，
- 如果 $P_i > right$，就代表我們需要用一個基地台來覆蓋 $[P_i, P_i + d]$ 這個範圍，並且將 $right$ 的值更新為 $P_i+d$
- 如果 $P_i \leq right$，就代表這個點已經被覆蓋了，所以可以直接跳過。
以下是 $f$ 的實作﹔
```cpp!
bool f(const vector<int>& P, int k, long long d) {
long long right{P[0] - 1};
for (auto Pi : P)
if (right < Pi) right = Pi + d, --k; // 新增一個新的基地台
return k >= 0;
}
```
時間複雜度為 $O(N)$。
現在我們就可以開始來做二分搜。
一開始需要先定義 $l, r$ 的初始值，因為 $1$ 也有可能是答案，因此 $l$ 一開始定為 $0$，而 $r$ 就是可能的最大直徑長度。
接下來就照著學過的方法實作二分搜，以下是範例程式，
```cpp!
int solve(vector<int>& P, int k) {
sort(P.begin(), P.end()); // 讓 P 為遞增
int l{0}, r{P.back() - P.front()};
while (r - l > 1) {
int mid{(l + r) / 2};
if (f(P, k, mid)) r = mid;
else l = mid;
}
return r;
}
```
總時間複雜度：$O(N \log{N} + N \log{C})$
> $C$ 為一開始 $l, r$ 的距離。
---
## 三分搜尋法（Ternary Search）
### 適用情境
:::success
一開始是嚴格遞增數列，到了某個元素後，轉為嚴格遞減數列（通稱凹向下）。
或是一開始是嚴格遞減，之後轉成嚴格遞增的數列（通稱凹向上）。
要搜尋的值為數列中的最值（absolute extrema）。
:::
注意到是**嚴格**遞增或遞減，代表此最值不會在陣列中出現第二次。
### 實作概念
首先需要定義要搜尋的範圍 $(l, r)$，
在此範圍內的元素總共有 $r - l - 1$ 個，若是只剩 $1$ 個元素，代表已經找到最值了，因此 $l + 1$（或 $r - 1$）就是我們要的索引值。
如果還有兩個以上，則我們可以找出兩個元素 $m1$ 和 $m2$ 來將此區間切分成長度相近的三個子區間。
接著再根據要搜尋的是最大值還是最小值，以及 $a_{m1}$ 和 $a_{m2}$ 的大小關係，來更新 $l, r$ 來縮小搜尋範圍。
每次範圍有可能縮為原本的 $\frac{2}{3}$，因此最多需要 $\lceil \log_{\frac{3}{2}}(r - l - 1)) \rceil$ 次操作。
時間複雜度：$O(\log_{\frac{3}{2}}(r - l - 1)) = O(\log{N})$
### 參考實作
```cpp!
/* 尋找陣列中的最大值 */
int ternary_seach(const vector<int>& a) {
int l{-1}, r{a.size()};
while (r - l - 1 > 1) { // 可以化簡為 r - l > 2
int m1{l + (r - l) / 3};
int m2{r - (r - l) / 3};
if (a[m1] > a[m2]) r = m2;
else l = m1;
}
return l + 1;
}
```
### 圖解
找出 $[-9, -3, 1, 6, 7, 10, 7, 3, 0]$ 的最大值的索引。
```graphviz
digraph {
l, m1, m2, r [shape = none]
array [label = "<-1>X|<0>-9|<1>-3|<2>1|<3>6|<4>7|<5>10|<6>7|<7>3|<8>0|<9>X", shape = record]
l -> array: -1
m1 -> array: 2
m2 -> array: 6
r -> array: 9
}
```
```graphviz
digraph {
l, m1, m2, r [shape = none]
array [label = "<-1>X|<0>-9|<1>-3|<2>1|<3>6|<4>7|<5>10|<6>7|<7>3|<8>0|<9>X", shape = record]
l -> array: 2
m1 -> array: 4
m2 -> array: 7
r -> array: 9
}
```
```graphviz
digraph {
l, m1, m2, r [shape = none]
array [label = "<-1>X|<0>-9|<1>-3|<2>1|<3>6|<4>7|<5>10|<6>7|<7>3|<8>0|<9>X", shape = record]
l -> array: 2
m1 -> array: 3
m2 -> array: 6
r -> array: 7
}
```
```graphviz
digraph {
l, m1, m2, r [shape = none]
array [label = "<-1>X|<0>-9|<1>-3|<2>1|<3>6|<4>7|<5>10|<6>7|<7>3|<8>0|<9>X", shape = record]
l -> array: 3
m1 -> array: 4
m2 -> array: 6
r -> array: 7
}
```
```graphviz
digraph {
l, m1, m2, r [shape = none]
array [label = "<-1>X|<0>-9|<1>-3|<2>1|<3>6|<4>7|<5>10|<6>7|<7>3|<8>0|<9>X", shape = record]
l -> array: 4
m1 -> array: 5
m2 -> array: 6
r -> array: 7
}
```
```graphviz
digraph {
l, r [shape = none]
array [label = "<-1>X|<0>-9|<1>-3|<2>1|<3>6|<4>7|<5>10|<6>7|<7>3|<8>0|<9>X", shape = record]
l -> array: 4
r -> array: 6
}
```
最後的答案就是 $l + 1$
---
### 例題
#### [Weakness and Poorness](https://codeforces.com/contest/578/problem/C)
:::info
定義一個數列的 poorness 是數列的總合的絕對值。
定義一個數列的 weakness 是所有連續子序列的 poorness 的最大值。
現在有整數數列 $a$ 以及一個實數變數 $x$，問數列 $[a_1 - x, a_2 - x, \dots, a_N - x]$ 的 weakness 最小可以為多少。
:::
> 題目的 $a$ 的索引值是從 $1$ 開始編號
我們先定義 $\displaystyle s(i, j) = \sum^j_{k \ = \ i}(a_k - x)$，
而題目的要求就可以寫成 $\displaystyle \max_{1 \leq i \leq j \leq N}|s(i, j)|$，接著我們需要再進一步化簡這個公式，過程寫在下面。
$$
\begin{align}
&\max_{1 \leq i \leq j \leq N}\lvert s(i, j)\rvert \\ =
&\max_{1 \leq i \leq j \leq N} \Big\{ \max(+s(i, j), -s(i, j)) \Big\} \\ =
&\max \bigg( \max_{1 \leq i \leq j \leq N}\left\{+s(i, j)\right\}, \max_{1 \leq i \leq j \leq N} \left\{-s(i, j)\right\} \bigg) \\ =
&\max(A, B)
\end{align}
$$
> $A, B$ 定義為對應的那兩段敘述。
$A$ 是一個對於 $x$ 的嚴格遞減的函數，且 $B$ 是嚴格遞增。
現在用 $\max()$ 把兩個函數合併，就會形成一個凹向上的函數，所以我們可以在上面找最小值。
接著我們就可以實作三分搜來找最小值，但注意這次是==在實數上三分搜==，不同於圖例的在整數上三分搜。
在開始三分搜之前，我們可以先來實作 $\displaystyle \max_{1 \leq i \leq j \leq N}\lvert s(i, j)\rvert$，從上面公式可以看出他就是最大連續和，因此直接用上週學到的技巧來實作。
```cpp!
double weakness(const vector<int>& a, double x) {
vector<double> dp(a.size());
dp[0] = a[0] - x;
double mx{dp[0]};
for (int i = 1; i < a.size(); ++i) {
dp[i] = max(dp[i - 1], 0.) + a[i] - x;
mx = max(mx, dp[i]);
}
dp[0] = -dp[0];
mx = max(mx, dp[0]);
for (int i = 1; i < a.size(); ++i) {
dp[i] = max(dp[i - 1], 0.) + x - a[i];
mx = max(mx, dp[i]);
}
return mx;
}
```
程式碼分成兩個非常相似的部分，第一部分就是最大連續和，第二部分是把原本數列乘上 $-1$ 之後再做一次最大連續和。
接下來三分搜的時候就可以直接用上面的 `weakness()` 來判斷 $m1, m2$ 的大小。
下面直接給範例程式，
```cpp!
double solve(const vector<int>& a) {
double l{-10001.}, r{10001.};
for (int i = 0; i < 100; ++i) {
double m1{l + (r - l) / 3};
double m2{r - (r - l) / 3};
if (weakness(a, m1) < weakness(a, m2)) r = m2;
else l = m1;
}
return weakness(a, (l + r) / 2);
}
```
這邊要注意到原本的 `while` 迴圈被換成了 `for` 迴圈，而且迴圈的結束條件也不一樣。
基本上，迴圈跑越多次結果會越準確，但是如果跑太多次就有可能會 <font color="#3498db">TLE</font>，所以在解題的時候必須要衡量一下到底要跑多少次才合適。
時間複雜度：$O(CN)$
> $C$ 為迴圈次數
---
## 練習題
| Problem | tags |
|:---------------------------------------------------------------------------------------------------------------:|:------------------------- |
| [Product Triplets](https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051066/0000000000051187) | `binary search` |
| [骨牌遊戲](https://tioj.ck.tp.edu.tw/problems/1432) | `binary search` |
| [隕石](https://tioj.ck.tp.edu.tw/problems/1337) | `binary search` |
| [Creative Snap](https://codeforces.com/contest/1111/problem/C) | `binary search`, `math` |
| [Coffee and Coursework (Hard Version)](https://codeforces.com/contest/1118/problem/D2) | `binary search`, `greedy` |
| [Cutting Out](https://codeforces.com/contest/1077/problem/D) | `binary search` |
| [Everyone is a Winner!](https://codeforces.com/contest/1263/problem/C) | `binary search`, `math` |
| [Searching Constellation](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0524)（題敘為日文，慎入） | `binary search` |
Sign in with Wallet
Connect another wallet