<style> .reveal .slides { text-align: left; font-size:28px; } </style> # sreach algorithm Introduction to Competitive Programming --- * 二分搜 * 三分搜 --- ## 二分搜 ### binary search 讓搜尋的範圍減少一半的方式 ---- ### 例題： 給一長度為 $n$ 的**已排序**陣列 $a$，以及 $m$ 個詢問，問你 $x$ 是否在 $a$ 之中。 ---- ### 做法一： 每次遍歷過整個陣列看 $x$ 是否在 $a$ 之中 複雜度：$O(n)$ ---- ### 做法二： 可以用陣列**已排序**的性質，二分搜陣列。 ---- 可以觀察到如果一個數字 $d$ 在陣列中比 $x$ 小， $x$ 如果有出現在陣列中，就一定在 $d$ 的右邊。 如果善用這個性質，每次就可以將搜索區間減少一半。 ---- 下面我們示範一下 在 $[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]$ 上詢問 $15$ 是否在陣列內 ---- ### 做法二： 一開始整個陣列都是有可能的範圍，所以 ```cpp= int l = 1, r = 10; ```  ---- ### 做法二： 看中間的位置是不是我們要的答案 ```cpp= int mid = (l + r) / 2; // mid = 5 ```  ---- ### 做法二： 發現不是而且發現 $arr[mid]$ 小於等於 $15$，所以左邊的區間不會有 $15$，因此我們將 $left$ 移到 $mid$ 的位置 ```cpp= if(arr[m] <= tar) { l = m; } ```  ---- ### 做法二： 接下來就一樣， 看中間的位置是不是我們要的答案  ---- ### 做法二：  ---- ### 做法二： 找到答案了！  ---- ### 做法二： 雖然這個範例沒有出現，但如果 $arr[mid]$ 大於 $15$ 時，$mid$ 的位置就不會是答案，因此我們會將 $right$ 移到 $mid - 1$ 的位置。 ```cpp= if(arr[mid] > tar) { right = mid - 1; } ``` ---- ### 程式碼： ```cpp= int l = 0, r = n - 1; while(l < r) { int m = (l + r) / 2; if(arr[m] <= tar) { l = m; } else{ r = m - 1; } } if(arr[l] == tar) { return 1; } return -1; ``` ---- ### 複雜度： 由於每次將區間切半，所以複雜度是 $O(\log_2n)$ ---- ### 二分搜的條件： 如果將已排序的陣列的 $index$ 跟值進行映射 ($x \rightarrow y$)，陣列就會變成單調遞增函數，二分搜就是在單調遞增的函數上進行搜尋。  ---- ### 例題：[APCS 基地台](https://zerojudge.tw/ShowProblem?problemid=c575) 很常見的二分搜例題 題意：在數線上給定 $n$ 個點，你可以在上面放 $k$ 個基地台，每個基地台可以服務左右 $\frac d 2$ 的範圍，詢問你 $d$ 最少需要多少？ $n, k, d$ 都是整數 ---- 先不管 $k$ 的限制，可以觀察到 $d$ 越小我們需要就需要越多的基地台，也就是 $k$ 跟 $d$ 成負相關，可以利用這個單調性來計算答案。 ---- 可以發現沒辦法直觀的利用 $k$ 來找到 $d$，但如果有 $d$ 時，計算 $k$ 會相對簡單。 假設有五個點 $[1, 2, 5, 7, 8]$， $d$ 等於 $5$ 時，要覆蓋到第一個點 $(1)$，基地台最遠可以放到 $3$ 的位置，而這個基地台最遠可以覆蓋到 $5$ 的位置，因此沒被覆蓋到的點只剩 $7、8$，我們在剛好只能覆蓋到 $7$ 的位置 $9$ 放下基地台，基地台就可以覆蓋全部的點了！ ---- 範例程式碼： ```cpp= int now = -1, d = 5, k = 0; for(int i = 0; i < n; i++) { if(arr[i] > now) { k++; now = arr[i] + d; } } cout << k; ``` ---- 通過上面的程式碼，我們這樣可以花 $O(n)$ 的時間找到 $k$，因此我們可以對 $d$ 二分搜，找出最小的 $d$ 會讓基地台的數量大於等於 $k$。 ---- 當搜出的數字比 $k$ 小時，我們就需要將右界向左縮，因為 $d$ 更大只會讓基地台的數量變少，相反的則是左界向右縮，只需要將二分搜跟上面的用 $d$ 去尋找 $k$ 的放在一起，就可以解出這題了。 ---- ```cpp= auto check = [&](int d) -> int{ int now = -1, ans = 0; for(int i = 0; i < n; i++) { if(arr[i] > now) { now = arr[i] + d; ans++; } } return ans; }; while(l < r) { int mid = (l + r ) / 2; int ret = check(mid); if(ret <= k) { r = mid; } else { l = mid + 1; } } ``` ---- ### 細節： 在二分搜之前要確認搜的東西是有單調性 (遞增、遞減)  ---- ### 細節： 確定答案有在左界跟右界內，沒有的話就只是白做工。 ---- ### 細節： 可以發現根據題目的不同，左界跟右界的縮法會不太一樣 ```cpp l = m, r = m - 1; l = m + 1, r = m; l = m + 1, r = m - 1; ``` 二分搜的重點就是看出題目的性質，決定要怎麼去搜。 **注意** 二分搜並不能只使用單種習慣的方法，需要使用題目的性質來變化你縮的方法。 ---- ### 細節： 承接上頁，決定縮法之後，還要決定 mid 要怎麼求，當縮到最小的時候，有可能因為左右界縮法的問題，就陷入無限迴圈。 當 `l=3, r=4, mid=(l+r)/2, l=m, r=m-1` 時 如果二分搜的結果是縮左界的話 `l` $\rightarrow$ `mid`，`3 `$\rightarrow$`(3+4)/2=3`，就會進入無限迴圈了！ 這裡的解法是將 `mid=(l+r+1)/2`，也就是從向下取整改成向上取整。 ---- ### 總結： --- ## 三分搜 ### ternary search ---- 顧名思義，二分搜是將區間分成兩半，三分搜就是分成三半。 不過為什麼需要三分搜呢？ 在什麼樣的情況下，分成兩份沒辦法解決問題，需要分成三份呢？ ---- 可以觀察到二分搜的條件 -- 單調函數，像是在一次函數上找某一個值。 那如果是找二次函數的極值呢？ ---- 好像沒辦法簡單的依靠 mid 來求出區間要往哪邊縮，不過三分搜要怎麼求二次函數的極值呢？ ~~雖然微分可以看出二分搜要往哪邊縮，但是如果是不是單純的二次函數，只是其中一邊單調遞減，其中一邊單調遞增，好像就沒辦法依靠對函數進行微分來求答案了~~ ---- 如果對以下函數找出極值，由於 f(ml) < f(mr) ，因此 ml 比 mr 離我們要的答案更近，所以我們會捨棄 [mr, r] 的區間，不過如果答案不在 [ml, mr] 之間呢？  ---- 可以觀察到在下圖的情況，我們一樣會捨棄掉 [mr, r] 的區間 只要根據誰的值離極值比較接近，我們就將另外一邊的區間捨棄掉，就可以三分搜出極值了！  ---- ### 實作程式碼 ```cpp= while(l < r) { int ml = l + (r - l) / 3; int mr = r - (r - l) / 3; if (check(ml) < check(mr)) { r = mr; } else { l = ml; } } ``` ---- ### 複雜度 每次切 $\frac{1}{3}$ 的區間，複雜度 $O(2 * \log_3n)$ ---- ### 三分搜的條件： 如果函數內有水平線的話，除非答案在水平線上，不然就不能對她三分搜了，如下圖所示，沒辦法直接知道要捨棄哪一邊的區間  ---- ### 例題： vitos family Vito 常拜訪親戚，所以想要找一間和所有親戚間總距離最小的房子住下來。輸入親戚數和門牌號，輸出最小距離和 ---- 對一個親戚來說，距離的公式是 $d_i(x) = |s_i - x|$，是一個單峰函數，而多個親戚的就是多個單峰函數的疊合，也是單峰函數，所以可以對 x 三分搜，找出單峰函數的極值。 複雜度 $O(\log n)$ 然後再花 $O(n)$ 時間計算最小距離和 總共 $O(n)$ ---- $f(x) = \sum\limits^n_{i = 1}|s_i - x|$ 可以發現任意兩個點 $s_i$、$s_j$，如果 $s_i \le x \le s_j$，$d_i(x) + d_j(x) = |s_j - s_i|$ 所以對 f(x) 來說，只要對所有的 $i、j$，x 符合上述條件，f(x) 就會是最小的 而正好中位數符合這個條件，因此這題我們只要選擇中位數，再花 $O(n)$ 的時間計算答案就可以解出來了 ---- ### 例題：最小包覆圓 平面上給 n 個點，在平面上任意位置畫一個圓，圓要包住所有的點，詢問半徑最少是多少 ---- ### 簡單化題目 平面上給 n 個點，在平面上 x = 0 上畫一個圓，圓要包住所有的點，詢問半徑最少是多少 ---- ### 再簡單一點 平面上給 1 個點，在平面上 x = 0 上畫一個圓，圓要包住所有的點，詢問半徑最少是多少 ---- 可以發現，對大圓來說，要覆蓋住一個點，半徑一定是點與線的最短距離，圓如果向上或是向下移動時，圓的半徑都要增加才能覆蓋住整個點，就會變成一個很典型的單峰函數。  ---- ### 回到前一題 可以發現在這題就變成多個單峰函數的疊合，而疊合後的單峰函數還會是單峰函數，因此我們就可以直接在 x = 0 上三分搜，搜出讓半徑最小的 y。 ---- ```cpp= struct node{ double x, y; }arr[n]; double check(double val) { double cmax = 0; for(int i = 0; i < n; i++) { cmax = max(cmax,(arr[i].x - 0) * (arr[i].x - 0) + (arr[i].y - val) * (arr[i].y - val)); } return cmax; } while(r - l > eps) { double ml = l + (r - l) / 3; double mr = r - (r - l) / 3; if (check(ml) < check(mr)) { r = mr; } else { l = ml; } } ``` --- ## 提單連結 https://vjudge.net/contest/596865#overview ---