搜尋 #4 ٩(｡・ω・｡)و

2019鐵人賽

2018-11-03 22:50:59

4393 瀏覽

分享至

二分搜尋

給定一個 N 長的單調數列，找目標值(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 開始。
可以參考：Why numbering should start at zero

總之，對於這個數列，可以用整數子集 [0, N) 寫下他的 index 範圍
這會比符號 [0, N-1] 來的簡潔一些。
而且若是問 [l, r) 的長度為何？只需計算 r-l
但問 [l, r]，就得計算 r-l+1
對所有自然數除以 P (P 也是自然數) 的餘數收集起來，會有 $\{[0], [1], .., [P-1]\}$ ，表達這件事只要寫 [0, P)
有時會需要用到空區間這個狀態，這時可以 [l, l)
事實上在 C++ 強大的 STL 中，迭代器也是以左閉右開區間來實作的。

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

關於輸出的約定

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

對於數列的 index 區間 [l, r)， lower & upper bound 都會落在 [l, r) 嗎？
欲搜尋的數如果大於整個數列，它最適合的位置就是 r (落在區間外囉)

所以對於所有可能輸出的 bound，可以用空區間表示：
也就是 [l, l), [l+1, l+1), .. , [r, r)
雖然意義上都是一個空區間，但看符號還能看出表達的 index 是啥

binary 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$ )

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

/* 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 中的lower_bound, upper_bound 函數還不夠對付所有問題，因應不同場合常得親自設計 (e.g. 三分搜、下降隱式數列)

範題 GCJ Kickstart Round G 2018 A Product Triplets：

仔細想想，雖然對數列排序後不會使 $O(N^3)$ 枚舉算出的答案不同
但排序後，當不考慮乘積為 0 的情況下，兩數積 $A_i \times A_j$ 保證會落在 j 後面，其中 i < j
這樣想，二分搜就有武用之地了！

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

sort(A, A+N);

long long int cnt = 0; //cnt := counter
for (int i = 0; i < N-1; i++) {
  for (int j = i+1; j < N; j++) {
    long long int 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^2log_2{N})$ 降到 $O(N^2)$ ，不過寫起來會稍微麻煩點。