<style> .reveal .slides { text-align: left; font-size:35px } </style> # Search Algorithm Introduction to Competitive Programming 2/7 ---- * 二分搜 * 三分搜 * Two Pointer --- ## 二分搜 ### 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 個基地台，每個基地台可以服務左右 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; } } ``` ---- ### 回到原問題 jakao 教我證明 :woozyface: --- ## 雙指針 --- two pointers 雙指針顧名思義，就是同時使用兩個指針，在序列、鍊錶結構上指向的是位置，在樹、圖結構中指向的是節點，通過或同向移動，或相向移動來維護、統計信息。(OI wiki) ---- ### 頭尾固定的雙指針 --- sliding window ---- ### 例題：[sliding windows maxmium](https://leetcode.com/problems/sliding-window-maximum/) 詢問每個大小為 k 的 sliding windows 的最大值 $-10^4 \le a_i \le 10^4$ ---- 用 multiset 維護 sliding windows 內的數字 ---- 程式碼： ```cpp= vector<int> ret; multiset<int> st; for(int i = 0; i < k; i++) { st.insert(nums[i]); } ret.push_back(*(st.rbegin())); for(int i = k; i < nums.size(); i++) { st.insert(nums[i]); st.erase(st.find(nums[i - k])); ret.push_back(*(st.rbegin())); } return ret; ``` ---- ### 例題： 給一個長度為 n、由非負整數組成的陣列 a，在 $\sum\limits^r_{i = l}a_i \le S$ 的情況下，最大化 r - l。 ---- ### 做法一： 用兩個迴圈遍歷所有 l, r，複雜度 $O(n^2)$ ---- ### 做法二： 因為是非負整數，問題可以轉換成對每個左界來說，右界最遠可以到哪邊， 所以我們維護一個前綴合，然後對陣列做二分搜，複雜度 $O(n\log n)$ ---- ### 做法三： 雙指針維護左界跟右界，被左界跟右界框起來的區域就是我們想要的，但是左界跟右界要怎麼移動呢？ ---- ### 做法三： 每次將右界向右移動一格，並當總和超過 s 時，將左界也向右移動。 ---- s = 20，初始化時，沒有包含任何區間。  ---- l = 1, r = 1, sum <= 20, r++  ---- l = 1, r = 2, sum <= 20, r++  ---- l = 1, r = 3, sum <= 20, r++  ---- l = 1, r = 4, sum <= 20, r++  ---- l = 1, r = 5, sum > 20, l++  ---- l = 2, r = 5, sum <= 20, r++  ---- l = 2, r = 6, sum > 20, l++  ---- l = 3, r = 6, sum > 20, l++  ---- l = 4, r = 6, sum <= 20, r++  ---- l = 4, r = 7, sum > 20, l++  ---- l = 5, r = 7, sum > 20, l++  ---- 結束了  ---- l 和 r 最多只會移動 n 步，複雜度 $O(n)$ ---- 程式碼： ```cpp= for(int i = 0; i < n; i++) { sum += arr[i]; while(sum > s) { sum -= arr[l]; l++; } ans = max(ans, i - l + 1); } ``` ---- ### 改變一下問題 給一個長度為 n、由非負整數組成的陣列 a 有幾組 l、r，$\sum\limits^r_{i = l}a_i \le S$ ---- 再觀察一下上一題 對 r = 4 來說，l = 1, 2, 3, 4 都符合 $\sum\limits^r_{i = l}a_i \le S$  ---- 因此本題就是在上一題的基礎上，對每個右界計算有幾個左界可以符合條件。 ---- 程式碼： ```cpp= for(int i = 0; i < n; i++) { sum += arr[i]; while(sum > s) { sum -= arr[l]; l++; } ans += (i - l + 1); } ``` ---- 遇到一個問題時，如果他是要求最好的區間或者是有幾個區間符合條件時，就可以考慮雙指針，指針要放哪，就要看題目而定了。 ---- ### 例題：[Container With Most Water](https://leetcode.com/problems/container-with-most-water/) 給一個為 n 的陣列 arr，$a_i$ 代表在 x = i 的位置有高度為 $a_i$ 的垂直線，選兩個位置 $i、j$ 且 $i < j$，計算 $\text{min}(a_i, a_j) * (j - i)$ 的最大值 ---- ### 做法一： 用兩個迴圈遍歷所有 l, r，複雜度 $O(n^2)$ ---- ### 做法二： 一開始先將指針放在最左邊跟最右邊，並比較兩邊的值，將值較小的指針往中間移，因為對這個指針來說，另外一邊的指針移動對答案是沒有貢獻的 ---- ### 程式碼： ```cpp= int maxa = 0; int l = 0, r = n - 1; while(l < r) { maxa = max(maxa, (r - l) * min(arr[l], arr[r])); if(arr[l] < arr[r]) { l++; } else r--; } ```