## 定義
從一堆資料中找到想要的資料，這就是搜尋，比如在一堆考卷中找到自己的考卷
有一個最簡單的方法，就是從頭開始一張張翻看名字，直到找到自己的考卷
## 線性搜尋
所謂的線性搜尋，就是剛剛說的方法，也是最直覺的方式

int l_search(int n, int cur) {
    for (int i=0;i<n;i++)
        if (a[i] == cur) // 找到了
            return i ;  // 回傳位置
    return n ; // 沒找到 回傳範圍外的值
}

這樣做的時間複雜度是 $O(n)$，如果要找的次數過多，數據的量過大，找起來就會非常耗時
所以這時候就會需要一個速度快一點的搜尋方式
## 二分搜尋
二分搜尋最簡單的例子就是在猜數字，猜 $1\sim 100$，每次都猜範圍的中間
如果用概念去想一下就知道，因為每次範圍都可以減半，所以找起來特別快
不過這麼快的搜尋速度是有條件的，就是陣列必須滿足單調性
所謂的單調性可以簡單理解成遞增或遞減，需要這個條件的原因比較重要
查找的時候需要判斷數值的大小關係，右(左)邊一定要皆 $\ge(\le)$ 中點
這樣才能透過判斷來縮減查找的範圍，而實作上需要用 sort() 或題目自帶滿足單調性
由於這種搜尋一次減少一半範圍的做法，二分搜的時間複雜度為 $O(log(n))$

int b_search(int n, int cur) {
    int L = 0, R = n ; // 範圍的左右端點

    while (L < R) {
        int M = (L+R) / 2 ; // 中間點
        if (a[M] < cur) // 點在右半邊
            L = M+1 ;    // 拋棄左半邊
        else if (a[M] > cur) // 點在左半邊
            R = M ;         // 拋棄右半邊
        else                  // 找到了
            return M ;
    }

    return n ; // 沒找到 回傳範圍外的值
}

不過這樣其實很容易寫錯，因為實作方式其實有很多種，比如上述就是用左閉右開的概念
換句話說就是判斷的範圍包含左邊，但不包含右邊，"純搜尋"建議用左閉右閉的方法
並且找 $\ge cur$ 的第一個位置，比較不會出錯，使用範圍也比較廣泛
不過在更進階的題目上，二分搜的使用需要更靈活，建議還是用推的會比較好
通常只要知道左右的開(閉合)情況，就可以快速地寫出對應的二分搜

int b_search_p(int n, int cur) {
    int L = 0, R = n-1 ;

    while (L < R) {
        int M = (L+R) / 2 ; // 中間點
        if (a[M] < cur) // 點在右半邊
            L = M+1 ;    // 拋棄左半邊
        else if (a[M] > cur) // 點在左半邊
            R = M-1 ;         // 拋棄右半邊
        else                  // 找到了
            return M ;
    }

    return L ; // return R 也可以
}

但在"只需要"搜尋的場合，還是會用 STL 內建的函式來解決

auto l_pos = lower_bound(v.begin(), v.end(), 6) ; // iterator
auto u_pos = lower_bound(v.begin(), v.end(), 6) ; // iterator

cout << "index: " << l_pos-v.begin() ; // position
cout << ' ' << u_pos-v.begin() << '\n' ; // position
cout << "value: " << *l_pos << ' ' << *u_pos << '\n' ;

實際上用到搜尋的例子會不僅限於"在資料內找到某數"的概念
在比較困難的題目就有可能會遇到其他方式的搜尋，比如"在範圍內找到最小可通過解"
這時候通常就會用搜尋+函式判斷是否能通過，一般都用二分搜
這種比較困難的題目，最後面會放一題相對簡單的，有興趣的可以試試看

## 例題-ZJ f071. 2. 刮刮樂 (Lottery)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f071)
解題思路 :
這題不難，就是判斷資料當中是否有對應的數字，並根據規則做加減
不過有幾個需要注意的地方，也算是題目敘述不足的部分
第一就是幸運數字可以重複使用，舉個例子，假設你的幸運數字是 $1$，號碼有五個 $1$
那這五個 $1$ 的獎金都可以被你拿走，第二個是幸運數字有可能相同
這個情況比較複雜，假設第一個跟第二個幸運數字相同，那一個號碼的獎金還是一份
假設第一(二)個跟第三個幸運數字相同，那因為獎金增加又減少，所以等於不變
至於搜尋的部分，因為這裡數字沒排序，而且只需要找 $3\times 5$ 次，所以用線性搜尋就好

#include<bits/stdc++.h>
using namespace std ;

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    int a, b, c ;
    cin >> a >> b >> c ;

    vector<int> v(5), m(5) ; // 輸入
    for (int i=0;i<5;i++)
        cin >> v[i] ;
    for (int i=0;i<5;i++)
        cin >> m[i] ;

    bool havec = false ; // 是否出現過 c
    int ans = 0 ;        // 總和
    for (int i=0;i<5;i++) {
        if (v[i] == a || v[i] == b) // 遇到 a 或 b (a == b 算一份獎金)
            ans += m[i] ;
        if (v[i] == c) {            // 遇到 c (注意 a== c or a == b)
            ans -= m[i] ;
            havec = true ;
        }
    }

    if (havec) // 有出現過 c
        cout << max(ans, 0) <<  '\n' ;
    else        // 沒出現過 c
        cout << ans*2 << '\n' ;
    return 0 ;
}

## 例題-ZJ d732. 二分搜尋法
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d732)
解題思路 :
題目問是否存在一個整數存在數列當中，通常用 lower_bound() 就可以了
因為 lower_bound() 是找大於等於的第一個數，所以找到的數可能不是題目要求的
如果找到的數跟題目要求的不同，那就代表沒找到，不過還有一種情況要考慮
如果題目要求的數字 $>$ 數列的最大數，那找到的位置就會是陣列的範圍外
所以這時候不能直接轉換成數字，而是要用 if 去把它過濾掉

#include<bits/stdc++.h>
using namespace std ;

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    int n, k ;
    cin >> n >> k ;

    vector<int> v(n) ; // 輸入
    for (int i=0;i<n;i++)
        cin >> v[i] ;

    int cur ;
    for (int i=0;i<k;i++) { // 找 k 個數
        cin >> cur ;
        
        // 二分搜找位置
        auto pos = lower_bound(v.begin(), v.end(), cur) ;
        if (pos == v.end() || *pos != cur) // 未找到
            cout << "0\n" ;
        else                               // 找到了
            cout << (pos-v.begin())+1 << '\n' ;
    }

    return 0 ;
}

注意我在第 $19$ 行有用到 if 的特性，所以 `pos == v.end()` 成立就不會判斷 `*pos != cur`
也就是前面說的小心使用到範圍外的位置，會導致錯誤

## 例題-ZJ f581. 3. 圓環出口
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f581)
解題思路 :
(建議先學過基礎演算法-前綴和與差分再解這題)
這題的題目敘述就有點不太好理解了，直接用題目的例子去理解會比較快
假設房間給與的點數分別為 $2,1,5,4,3,5,3$，要求的點數分別為 $8,9,12$
那第一個要 $8$ 點，所以 $2+1+5 = 8$，停下來的地方是 "點數為 $4$ 的房間"
所以是滿足條件後的一個房間，第二個要 $9$ 點，所以 $4+3+5=12$
從 $4$ 開始，所以每次都是從停下的地方開始加，加到滿足後再往後一個房間
接下來就是如何快速找到滿足條件的房間，這裡就需要用到前綴和了
因為前綴和可以快速計算兩個房間路徑上的點數總和，不過有些問題
假設要從第 $5$ 間房間到第 $3$ 間房間，一般的前綴和就無法輕鬆解決
所以我們可以把前綴和擴充，把最後一間到第一間到...到最後二間的前綴和也加進去

vector<int> pre(2*n-1) ; // 前綴和
for (int i=0;i<n;i++) {
    cin >> pre[i] ;
    pre[i] += pre[i-1] ; // 直接計算前綴和
}

for (int i=n;i<2*n-1;i++) // 把前綴和拆成 pre[n-1] 與其他
    pre[i] = pre[n-1] + pre[i%n] ;

這樣就如果需要 need 個點數，用二分搜找 `pre[(pos+n-1)%n]+need` 就可以找到滿足條件的位置
最後在記得把位置往後一位，然後把位置取 $n$ 的餘數，因為前綴和的大小超過 $n$

#include<bits/stdc++.h>
using namespace std ;

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    int n, m ;
    cin >> n >> m ;

    vector<int> pre(2*n-1) ; // 前綴和
    cin >> pre[0] ;

    // 前綴和
    for (int i=1;i<n;i++) {
        cin >> pre[i] ;
        pre[i] += pre[i-1] ;
    }
    for (int i=n;i<2*n-1;i++)
        pre[i] = pre[n-1] + pre[i%n] ;

    int need, pos = 0 ;
    for (int i=0;i<m;i++) {
        cin >> need ;
        
        // 找到滿足條件的位置
        auto np = lower_bound(pre.begin(), pre.end(), pre[(pos+n-1)%n]+need) ;
        pos = (np-pre.begin()+1) % n ; // 再往後一間
    }

    cout << pos << '\n' ;
    return 0 ;
}

## 例題-ZJ f815. TOI_y21m4_a01遊戲升等
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f815)
(這題是比較困難的題目，如果能看得懂就看，看不懂可以先跳過)
解題思路 :
首先要說明，如果升兩等不可以升兩次一等，題目好像沒說，在這裡補充一下
再來就是計算每個角色升到 $x$ 等的花費有沒有超過持有的金幣，這個應該不難，用 for-loop

bool cost(vector<int> &v, int lvl) {
    // 如果都升到 lvl，需要花費的金幣有沒有在 c 之內
    LL now = 0 ;
    for (int i=0;i<n;i++) { // 計算需要花費多少金幣
        if (lvl > v[i]) {    // 需要升級
            now += (LL)(lvl-v[i])*(lvl-v[i]) ;
            if (now > c)      // 花費超過 c
                return false ;
        }
    }
    return true ; // 算完沒超過 c
}

接下來才是比較困難的地方，就是要找到滿足條件的最大可能，最簡單的方式就是線性搜尋
也就是從 $1$ 開始，慢慢數字往上加，就可以找到滿足條件的最大可能了

for (int i=1;i<m;i++) {
    if (!cost(i)) {
        cout << i-1 << '\n' ;
        return 0 ;
    }
}

不過這樣的做法時間複雜度有點高，假設等級範圍是 $0 \sim m$，時間複雜度就是 $O(nm)$
可能有人不知道等級範圍怎麼算，其實只要考慮最極端的情況就可以了
首先金幣只花在一個人，升的等級肯定最多，再來那個人本身的等級越高越好
所以金幣最多 $10^{14}$，可以升 $10^7$ 等，角色原先最多 $10^7$ 等，加起來最多 $2\times 10^7$
那已經知道線性搜尋效率太差，那要不要試試看二分搜，畢竟概念上可以把可能性看陣列
陣列的內的元素就會像這樣: $\{cost(1), cost(2), ..., cost(m)\}$
那就可以用二分搜去找滿足條件的最大值，不過跟一般的二分搜不太一樣

#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;

int n ;
LL c ;

bool cost(vector<int> &v, int lvl) {
    // 如果都升到 lvl，需要花費的金幣有沒有在 c 之內
    LL now = 0 ;
    for (int i=0;i<n;i++) { // 計算需要花費多少金幣
        if (lvl > v[i]) {    // 需要升級
            now += (LL)(lvl-v[i])*(lvl-v[i]) ;
            if (now > c)      // 花費超過 c
                return false ;
        }
    }
    return true ; // 算完沒超過 c
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;

    cin >> n >> c ;

    vector<int> v(n) ;
    for (int i=0;i<n;i++)
        cin >> v[i] ;

    // 用二分搜去找滿足條件的最大可能
    int L = 0, R = INT_MAX ;
    while (L <= R) { 
        int M = (L+R) / 2 ;
        if (cost(v, M)) // 滿足條件
            L = M+1 ;
        else             // 不滿足條件
            R = M-1 ;
    }
    cout << R << '\n' ;

    return 0 ;
}

這個二分搜跟我們上面介紹的有點不一樣，只要用推的去理解就可以發現差異帶來的影響
二分搜只要考慮三種問題，第一是能不能找到對的值，第二是能不能停下來，第三是答案是 L 還是 R
通常會卡在第二與第三，考試或檢定通常會有紙，記得用比較小的情況推一下才不會出錯