2020 競技程設教材 HackMD Book

2019 Week 5: Searching

這週要介紹搜尋方法不會以圖的方式介紹，而是用數列

子集生成

顧名思義，就是將 set 的所有子集挑出來，所有可能子集的集合又稱冪集合^[1]
例如

$\{A,B\}$ 的所有子集為

$\{\mathrm{\varnothing },\{A\},\{B\},\{A,B\}\}$

遞迴法

void powerset(int dep) {
  if(dep == N) {
    for (int i = 0; i < N; i++) printf("%d ", bit[i]);
    putchar('\n');
    return;
  }
  
  bit[dep] = 1;
  powerset(dep+1);
  bit[dep] = 0;
  powerset(dep+1);
}

$N=3$ 將輸出：

1 1 1 
1 1 0 
1 0 1 
1 0 0 
0 1 1 
0 1 0 
0 0 1 
0 0 0 

二進制法

for (int i = 0; i < (1<<N); i++) {
  for (int p = 0; p < N; p++) printf("%d ", bool(i&(1<<p)));
  putchar('\n');
}

$N=3$ 將輸出：

0 0 0
1 0 0 
0 1 0 
1 1 0 
0 0 1 
1 0 1 
0 1 1 
1 1 1 

在許多場合，我們不一定只有 0 和 1 兩種佔位符 (placeholder)，可能有三種甚至更多
所以遞迴法或許比二進制法還要更為泛用。

二分搜尋 (binary search)

有許多文章介紹二分搜並沒有交代好前提，而是採用大量案例分析去佐證二分搜的實作很正確。
我認為這樣不優，這裡會花較多的篇幅把一些約定俗成的事情交代清楚再給出實作

給定一個

$N$ 長的單調^[2]數列，找目標值(target)的位置
當目標有 1 個以上，這時有兩種位置： upper bound 與 lower bound

考慮數列

$0,3,3,3,5,8,9$，當目標為

$3$：

• 可能的 lower bound index 為 0, 1
• 可能的 upper bound index 為 3, 4, 5, 6, 7, ..

當然，通常會希望 upper bound 與 lower bound 越緊越好
所以上面拿的 upper bound 要是 3、lower bound 要是 1 才好？

信仰

在繼續進到實作之前，先討論信仰
upper bound 與 lower bound 真的越緊越好嗎？
以上面例子，有沒有可能 lower bound 取 0、upper bound 取 4 在應用中會比較易用？

左閉右開區間

$[l,r)$

給定長度

$N$ 的數列

$A_0,A_1,..,A_{N-1}$

大部份習慣數數從

$1$ 開始數，因為應用在數個數時，當數到最後一數，剛好就是要求的個數。
但根據皮亞諾公設對自然數的定義，數應該要以

$0$ 為起點；甚至在許多程式語言實作中，陣列的 index 是從 0 開始^[3]。

• 總之，對於這個數列，可以用整數子集

  $[0,N)$ 寫下他的 index 範圍
  這會比符號
  $[0,N-1]$ 來的簡潔一些。

• 而且若是問

  $[l,r)$ 的長度為何？ 只需計算
  $r-l$
  但問
  $[l,r]$，就得計算
  $r-l+1$

• 對所有自然數除以

  $P$^[4] 的餘數收集起來，會有
  $\{[0],[1],..,[P-1]\}$，表達這件事只要寫
  $[0,P)$

• 有時會需要用到空區間這個狀態，這時可以

  $[l,l)$

• 先前多次提及的，C++的 STL 中，迭代器是以左閉右開區間來實作的。

講這麼多左閉右開區間的好(?)，回到信仰話題，
普遍實作中會認為 lower bound 為 1、upper bound 為 4 會比較好。
(以後 lower bound & upper bound 若沒特別設定，都依此慣例)

關於輸出的約定

若要搜尋的數不在數列中，那應該輸出哪個 index？
普遍實作會輸出當此數插入到這個數列中它最適合的位置
何謂最適合？就是要保持著數列仍然單調^[5]。

對於數列的 index 區間

$[l,r)$， lower & upper bound 都會落在

$[l,r)$ 嗎？
欲搜尋的數如果大於整個數列，它最適合的位置就是

$r$ (落在區間外囉)

而對於所有可能輸出的 bound，可以用空區間表示：
也就是

$[l,l),[l+1,l+1),..,[r,r)$^[6]
雖然意義上都是一個空區間，但看符號還能看出 表達的 index 是啥

linear search 找 lower bound

來實作找 lower bound 的演算法吧：
假設

$[k,k)$ 就是 lower bound，那麼對於原區間

$[l,r)$，就是設法把

$[l,r)$ 壓縮至

$[k,k)$

簡單的作法就是，一直遞增左界：

$[l,r),[l+1,r),..$ 直到碰到

$[k,r)$

• 最後發現
  $A_k$ 就是目標，這樣就能求得
  $[k,k)$
• 或著發現
  $A_k$ 大於目標，
  $[k,k)$ 還是解 (最適合原則)

while (l != r) {
  int m = l;
  if (A[m] >= target) r = l;
  else l = m + 1;
}

return l;

另一個從右界遞減的演算法：

while (l != r) {
  int m = r - 1;
  if (A[m] >= target) r = m;
  else l = r;
}

return l;

兩個演算法都使 l, r 相等且得到

$l=r=k$ 與

$[k,k)$

binary search 找 lower bound

回到小節標題，二分搜？這名字就是演算法的動機，將數列切成兩份以做到搜尋：
將上述演算法合併起來會得到

/* random lower bound search*/
while (l != r) {
  int m = l + rand()%(r-l); // 切成兩份
  if (A[m] >= target) r = m;
  else l = m + 1;
}

return l;

因為不知道 m 該遵從哪個演算法，就改成在區間中隨機挑了
這一步非常重要，先思考這樣寫真的正確嗎？

而 lower bound 普遍的二分搜實作，就僅把 m 改成均等的兩份：

int m = (l+r)/2;

m 其實就是 middle 的縮寫哦

而 upper bound 的二分搜實作也是類似的：

/* upper bound */
while (l != r) {
  int m = (l+r)/2;
  if (A[m] <= target) l = m + 1;
  else r = m;
}

return l;

二分搜複雜度為

$O({\log }_2(r-l))$, 其中

$l,r$ 為初始左界右界。

同學就跟著 lower bound 的發明過程，試實作 upper bound 二分搜！
光只會使用 STL 中的std::lower_bound, std::upper_bound 函數還不夠對付所有問題，因應不同場合常得親自設計 (e.g. 三分搜、隱式數列)

範例 GCJ Kickstart Round G 2018 A Product Triplets：

在第二週教材的練習中，這題的 small dataset 很輕易的就能用枚舉做出來，但對於 large dataset，

$O(N^3)$ 就不夠快了。

仔細想想，雖然對數列排序後不會使

$O(N^3)$ 枚舉算出的答案不同
但排序後，當不考慮乘積為

$0$ 的情況下，兩數積

$A_i\times A_j$ 保證會落在

$j$ 後面，其中

$i<j$
這樣想，二分搜就有武用之地了！

乘積

$0$ 的情況比較特殊一點，但也不難處理：

sort(A, A+N);

long long cnt = 0; // cnt := counter
for (int i = 0; i < N-1; i++) {
  for (int j = i+1; j < N; j++) {
    long long t = A[i]*A[j]; // t := target
    if (t || !A[j]) cnt += upper_bound(A+j+1, A+N, t) - lower_bound(A+j+1, A+N, t);
    else cnt += upper_bound(A+i+1, A+j, 0) - lower_bound(A+i+1, A+j, 0);
  }
}

此題其實還能讓複雜度從

$O(N^2{\log }_{2}N)$ 降到

$O(N^2)$，不過寫起來會稍微麻煩點。

範例 TIOJ 1432 骨牌遊戲：

int const maxn = 1001 + 10;

簡單的，採用枚舉的方式去找出哪個"最大傷害強度"是可行的
把可行的"最大傷害強度"找出來，接著在其之中把最小值輸出就行了

首先做出一個可判定此"最大傷害強度"是否可行的函數：

bool check(int strength) {
  int cost = 0, cnt = 0;

  for (int i = 0; i < n; i++) {
    cost += s[i];
    if (cost > strength) cost = s[i], cnt++;
  }

  return cnt <= w;
}

接著枚舉一下：

int l = *max_element(s, s+n), r = maxn*maxn;
for (int i = l; i <= r; i++)
  if (check(i)) return i;

可以發現到，第一個遇到可行的"最大傷害強度" (strength) 就是題目要求的最終答案。
但可惜的是，這樣

$O(N^3)$ 複雜度明顯會 TLE

其中

$N^2$ 來自於 r = maxn*maxn

研究一下 check 函數可知，因為每次把 strength 條大，會造成 cnt 越來越小，所以返回的 bool 值形成一個單調數列，
於是，可以使用二分搜去改進原本枚舉的做法：

while (l != r) {
  int m = (l+r)/2;
  if (check(m)) r = m;
  else l = m+1;
}

return l;

複雜度改進成

$O(N\log N^2)\approx O(N\log N)$

練習：

Sprout OJ 48 二元搜尋樹
AIZU Online Judge 0524 星座探し
CODEFORCES 1118D Coffee and Coursework
GCJ Kickstart Round G 2018 B Combining Classes: Small dataset
CODEFORCES 1263C Everyone is a Winner!
CODEFORCES 1077D Cutting Out

---

1. Wikipedia/ Power set ↩︎

2. 單調：可以是升序或降序的數列 ↩︎

3. Why numbering should start at zero (Dijkstra, Edsger Wybe (May 2, 2008)) ↩︎

4. 當然

   $P$ 也屬於自然數 ↩︎

5. 遞增或遞減 ↩︎

6. 為什麼不用左閉右閉區間？其實在這邊兩者各有優點，同學自行思考 ↩︎