【C++】競程筆記（搜尋演算法、習題練習）
===

[TOC]

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

---

線性搜尋法（linear search）
---

時間複雜度為 $O(N)$ ，就是用 for 迴圈遍歷得出的結果，如下：

#include <iostream>
#include <vector>

using namespace std;

int main(){
    
    vector <int> a = {2,1,7,2,4,3,0,11,3,4,5,5,6,7,100,92,41,27,14};
    
    for (int i=0;i<a.size();i++){
        if (a[i] == 100){
            cout << i;
            break;
        }
    }
    return 0;
}

以上程式碼透過遍歷尋找 100 這個元素的位置，最終輸出結果為 14。

二分搜尋法（binary search）
---

:::success
使用此搜尋法前需要將資料進行「排序」。
:::

二分搜將已排序好的序列二分為一，分為左右兩邊，取中間值後，若發現此中間值比欲搜尋值大，那麼就往左查找，反之往右。

那往左、往右之後呢，就是繼續二分，不斷「切割」序列，直到找到值為止。

時間複雜度： $O(log N)$

// arr 是我們要搜尋的序列 (由小到大排列好的)、len 是序列的長度、tar 是
// 我們要搜尋的目標。
// 回傳值為目標的索引值。
int bin_search (int arr[], int len, int tar) {
    int l = 0, r = len;         // 答案候選區間 (左閉右開)。
 
    while (l < r) {
        int m = l + (r - l) / 2;  // 猜中間的。
        if (arr[m] < tar)
            l = m + 1;              // 猜的太小，更新候選區間為右半邊。
        else if (arr[m] > tar)
            r = m;                  // 猜的太大，更新候選區間為左半邊。
        else
            return m;               // 猜中了。
    }
 
    return len;                 // 沒找到，回傳 len。
}

### binary search in STL
---

* std::binary_search(start, end, val);
* std::upper_bound (first, last, val, comp);
* std::lower_bound (first, last, val, comp);

前三個參數 first, last, val 分別為：從序列容器哪裡開始、從序列容器的哪裡結束、要求什麼值。

comp 為比較函數，要跟 val 比較值，為 optional 的選項，這個函數帶有兩個參數，然後最後要回傳布林值。如果範圍內的元素小於 val，則回傳 true，否則回傳 false。

upper_bound -> 找上限；lower_bound -> 找下限。

而兩者差異如下表（作者繪製）：

| | lower_bound | upper_bound |
| -------- | -------- | -------- |
| 回傳位置 | 第一個 ≥ val 的元素位置 | 第一個 > val 的元素位置 |
| 當 val 存在時 | 指向 val 首次出現的位置 | 指向 val 最後一次出現後的下一個位置 |
| 當 val 不存在時 | 指向第一個大於 val 的元素 | 指向第一個大於 val 的元素 |
| 當 val 大於所有元素時 | 回傳 last | 回傳 last |

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 3, 3, 5, 7, 9};

    auto it = lower_bound(vec.begin(), vec.end(), 3);
    cout << "lower_bound of 3 at index: " << (it - vec.begin()) << endl;

    it = lower_bound(vec.begin(), vec.end(), 4);
    cout << "lower_bound of 4 at index: " << (it - vec.begin()) << endl;

    return 0;
}

output:

lower_bound of 3 at index: 1
lower_bound of 4 at index: 3

auto it = std::upper_bound(vec.begin(), vec.end(), 3);
std::cout << "upper_bound of 3 at index: " << (it - vec.begin()) << std::endl;

output:

upper_bound of 3 at index: 3

可用來計算某個值在序列容器裡面出現的次數：

int count = std::upper_bound(vec.begin(), vec.end(), val) - 
            std::lower_bound(vec.begin(), vec.end(), val);

### 二分搜範例
---

LeetCode 3Sum：https://leetcode.com/problems/3sum/description/

給定一個序列 `[nums[i], nums[j], nums[k]]` 被叫做三胞胎（triplets），然後 $i \neq j \neq k$ ，找出 `num[i] + nums[j] + nums[k] = 0`。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
    vector<vector<int>> result;
        
    int n = nums.size();
        
    if (n < 3) return result;

    sort(nums.begin(), nums.end());

    if (nums[0] > 0 || nums[n - 1] < 0) return result;

    for (int i = 0; i < n - 2; i++){
        
        if (nums[i] > 0) break;

        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = n - 1;

        while (left < right){
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum < 0){
                // 若和 < 0
                left ++;
                
            } else if (sum > 0){
                // 若和 > 0
                right --;
                
            } else{
                // 這邊找到解了!
                
                result.push_back({nums[i], nums[left], nums[right]});

                while (left < right && nums[left] == nums[left + 1]) left ++;
                
                while (left < right && nums[right] == nums[right - 1]) right --;

                left ++;
                right --;
            }
        }
    }
    return result;
    }
};


排序完後可以加一個判斷提速：`if (nums[0] > 0 || nums[n - 1] < 0) return result;`

因為預設的排序肯定都會是升序，所以如果第一個元素 > 0，則後面都是 > 0 了，不可能有 < 0 的情況出現，可直接回傳空的 vector，避免後續運算。

在 for 裡面，有條判斷：`if (nums[i] > 0) break;`，因為題目要求的是三項加起來 = 0，所以萬一有一項是 > 0，那就不妙了，所以直接 break（再強調：因為資料排序過了，所以可以這樣做）。

而 `if (i > 0 && nums[i] == nums[i - 1]) continue;` 是為了避免出現重複的數字（目前數字跟前面一項相同）。

之後 27 行以下都是二分搜的部分了。

搜尋法習題練習
---

1. leetcode sqrt(x) : https://leetcode.com/problems/sqrtx/description/

這題千萬不要直接引入 sqrt(x) 函數喔XD，因為要透過原理去求平方根近似值。

那這原理是啥呢？十分逼近法（二分搜）。

#include <iostream>

using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        
        int left = 1, right = x, ans = 0;

        while (left <= right){
            long long mid = left + (right - left) / 2;
            long long square = mid * mid;

            if (square == x) return mid;
            else if (square < x){
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
};


二分搜的效率已經算很快了，但還有更快的解法，就是牛頓法求近似值。牛頓法是利用 limit 跟微分出來的結果。

具體公式如下：

$x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}$

那這題要求的是平方根，所以我們推導一下公式：

令 $f(x) = x^{2} - m$

當 $x^{2} - m = 0$ ，則 $x = \sqrt m$ 。這是我們要求的東西。

$f'(x) = 2x$ ，我們的一階導函數求出來了，而 $m$ 等於 $x^{0} \cdot m$ ，屬於常數項，所以直接消失 bang 不見。

之後再將 $f(x)$ 跟 $f'(x)$ 代入公式內，得到：

$$x_{n+1} = x_{n} - \frac{x^{2}_{n} - m}{2x_{n}}$$

經過通分跟一些處理過後，得到：

$$x_{n+1} = \frac{x_{n} + \frac{m}{x_{n}}}{2}$$

然後就可以開始寫程式了：

#include <iostream>

using namespace std;

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        long long r = x;
        while (r * r > x){
            r = (r + x / r) / 2;
        }
        return r;
    }
};


2. 2020 年 7 月 APCS 第三題，圓環出口：https://zerojudge.tw/ShowProblem?problemid=f581

**題目解說：**

有 $n$ 個房間（編號由 $0$ 到 $n-1$ ），形成環狀結構。

* 每個房間 $i$ 都可走到房間 $(i+1)$ $mod$ $n$。
* 如：當 $n = 5$ ，房間為 $0→1→2→3→4→0→1 \cdots$ 循環移動。

每個房間 $i$ 進入時會獲得對應的點數 $p_{i}$ ，最初從房間 $0$ 出發，並依照 $m$ 個任務來行動。

**解題目標：**

依序完成 $m$ 個任務，對於每個任務 $p_{i}$ ，至少要累積到 $q_{i}$ 個點數，然後停到某個房間 $t$ 。之後，下一個任務的起點就變成房間 $(t+1)$ $mod$ $n$ 。

最後要計算完成第 $m$ 個任務後會停在哪個房間。

**統整一下要做的事情：**

1. 從當前房間開始累積點數，直到點數累積到目標 $q_{i}$ 。
2. 當點數達標時，停在最後進入的房間，然後下一次的起點變為 $(t+1)$ $mod$ $n$ 。
3. 若點數累積到房間 $n - 1$ 還沒達標，則需要從房間 $0$ 繼續累積（因為房間為環狀的）。

這題使用到前綴和求和會更快，而至於要快速找到最後停留的房間，則使用二分搜會更好，因為 n 會很大，所以線性搜尋絕對穩死。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    
    cin >> n >> m;
    
    vector<long long> p(n), prefix(n+1, 0);
    
    for(int i=0; i<n; i++){
    
        cin >> p[i];
        prefix[i+1] = prefix[i] + p[i];
        
    }
    
    long long total = prefix[n]; // 一圈總和
    
    int start = 0;
    
    for(int i=0; i<m; i++){ // 執行 m 個任務
    
        long long q;
        cin >> q;
        
        // 若從start到房間n-1的累積點數>=q，則在prefix中找prefix[start] + q的下限
        
        if(prefix[n] - prefix[start] >= q){
        
            long long target = prefix[start] + q;
            // 在區間 [start+1, n] 中搜尋
            int j = lower_bound(prefix.begin()+start+1, prefix.end(), target) - prefix.begin(); // 求索引 j
            // 完成任務的房間為 j-1
            start = (j) % n; // 下一個起始房間是 (t+1) mod n，其中 t = j-1
            
        }
        
        else{
        
            long long rem = q - (prefix[n] - prefix[start]);
            // 從前綴和中搜尋，區間 [0, n] 中找 prefix[j] >= rem
            int j = lower_bound(prefix.begin(), prefix.end(), rem) - prefix.begin();
            start = (j) % n; 
            
        }
        
    }
    
    cout << start << "\n";
    return 0;
    
}