## 定義
通常我們在解決關於二分搜的問題，可能會配合其他演算法進行，比如排序+搜尋
比如兩個陣列找兩元素相加等於某數這種題目，二分搜都會在一個已經明確知道的範圍內進行
不過 APCS 的第四題中會出現一種用法，就是二分搜找答案範圍
這個方法通常是在具有單調性的解答範圍內找出第一個符合條件位置或對應的值
當然這種概念還是太過複雜了，APCS 中大部分題目可以用下面的圖片表示
箭頭指向的就是題目要求的答案，或是計算過程中必須的解答
圈圈是代表符合題目的條件，實際上最後的答案應該都是一個數字
### 被隱藏的單調性與實作
單調性簡單來說就是不嚴格遞增與遞減，這種題目的可能答案通常具有這種屬性
假設我們拿一個陣列代表題目的可能答案 $a_1, a_2, ..., a_n$
前面說了題目有遞增或遞減，假設 $a_i$ 會越來越大，那就會跟前面的圖片一樣
在要求 $a_i >= k$ 且 $a_i$ 越小越好的情況下，箭頭指向就是最終答案
而要怎麼找到箭頭呢，因為遞增的陣列，實際上就是已經排序的陣列，這時候就可以使用二分搜
中點 $>= k$ 那就將右端修改成目前終點然後繼續下一輪二分搜
當然使用跳躍二分搜也行，目前跳的位置 $< k$ 那就先跳過去然後繼續下一輪
概念都是相同的，目的是為了找到第一個 $>= k$ 的位置
大致上都會是下面這個邏輯

while 左端 < 右端-1
    if 中點對應的值符合條件
        右端 = 兩端中點
    else
        左端 = 兩端中點

以下二選一
return 函式(右端)
return 右端位置

總而言之，這些敘述可能還是太乾了，沒辦法讓你理解，所以我們直接看第一個例題
### j125. 4. 蓋步道 (2022年10月APCS第四題)
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j125)
這題簡單來說就是找到從左上走到右下的高度差，然後判斷在這個高度差下的最短路
最短路各位應該還行，因為給你高度差的情況下，只要用 BFS 就能輕鬆解決
那單調性是怎麼看出來的呢 如果在 k 高度差能走的路徑，在 k+1 也能走
甚至如果你將高度差拉到最大值，你可以用一定最短的距離解決
所以高度差變大只會讓最後的路徑越短或相同，那這不就是路徑長的遞減嗎
只要把高度差當成 index，值就是最短路徑的長度，那整個陣列應該就是遞減的
不過可能有人注意到了，以這題來說，高度差不夠等於過不去，並不是一個數字
別忘記我們前面講的，符合條件的第一個位置，所以前面的數字用不到所以沒關係
而後面的可能解一定有單調性，所以才能使用這個方法(應該說大部分題目都是這樣)

如果用線性搜尋會花費 $O(n)$ 的時間(這題是 $O(h)$)
所以完整的時間複雜度就是 線性搜尋 $\times$ BFS，也就是 $O(hn^2)$
依照題目限制，執行時間肯定會超過 APCS 規定的一秒，那如果用二分搜呢
因為最大高度差是 $10^6 - 1$，所以我們用二分搜去做時間複雜度會大幅降低
基本上是 $O(n^2log(h))$，時間滿充裕的

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

struct locat {
    int x, y, w ; // x, y, step(way)
};

int n, m ;
int high[305][305] ;
int mm[4][2] = {0,1, 0,-1, 1,0, -1,0} ; // movement

bool ir(int x, int y) { // (x, y) is in range
    return x >= 0 && x < n && y >=0 && y < n ;
}

bool visit[305][305] ;

int bfs() {
    queue<locat> que ;
    que.push({0, 0, 0}) ;
    visit[0][0] = true ;

    while (!que.empty()) {
        locat it = que.front() ;
        que.pop() ;

        if (it.x == n-1 && it.y == n-1) // got it
            return it.w ;

        for (int i=0;i<4;i++) { // up down left right
            int nx = it.x+mm[i][0], ny = it.y+mm[i][1] ;

            if (ir(nx, ny) && !visit[nx][ny]) { 
                int nh = abs(high[it.x][it.y]-high[nx][ny]) ;
                if (nh <= m) { // new road
                    visit[nx][ny] = true ;
                    que.push({nx, ny, it.w+1}) ;
                }
            }
        }
    }

    return -1 ; // can't
}

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

    int L = 0, R = 1e7, ans ;
    cin >> n ;
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            cin >> high[i][j] ;

    int tmp ;
    while (R-L > 1) { // 二分搜
        m = L + (R-L) / 2 ; 
        memset(visit, false, sizeof(visit)) ; // reset visit
        tmp = bfs() ;
        if (tmp != -1) { // can
            R = m ;
            ans = tmp ;
        }
        else            // can't
            L = m ;
    }

    cout << R << '\n' << ans << '\n' ;

    return 0 ;
}

在上面的程式碼就是用二分搜去找符合條件並且最小的高度差
然後因為條件是能從左上走到左下，剛好可以用 BFS 去跑
所以我在這裡直接把二分搜的過程結合 BFS，這樣就可以省去最後跑 BFS 的時間
最後的時間複雜度是 $O(log(h)n^2)$
這是近年比較簡單的題目，只用了 BFS + 二分搜就可以解決

那來看一題比較簡單的歷屆，是比較早期的
### c575. APCS 2017-0304-4基地台
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c575)
這題是比較簡單的題目，要設立基地台(有數量上限)，且要覆蓋所有點
然後在滿足條件的情況下，基地台的覆蓋直徑越小越好
這題其實也能比較直觀的看出單調性，但我們可以先縮減一下情況
假設只需要覆蓋兩個點，所以在哪一點放基地台都沒差
那直徑 k 的基地台能覆蓋到的點，直徑 k+1 的基地台也能
也就是說，直徑越大的基地台能夠以更少的數量覆蓋所有的點
那麼如果把直徑當成 index，最少基地台數量當成值
整個陣列會是遞減的，也就是具備了單調性

接下來說明一下如何找出最少基地台的數量
如果從左往右看，假設基地台"半徑"為 m，對於第一個點 X 來說
一定會有一個基地台在點 N (N <= X + m)，並且一定是第一個基地台
因為這個基地台它可以涵蓋 $[N-m, N+m]$，這就包含 X $\sim$ N 中的所有點
所以在 X $\sim$ N 之間不需要再加入任何基地台，也所以一定是第一個基地台
接下來就簡單了，你處理了 $[N-m, N+m]$，那在範圍外的點不就能從頭開始
只要把範圍外的第一個點當作剛剛敘述的第一個點，如此往復的操作
最後整個範圍都能被基地台包進去，也就能夠解決這個題目

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

LL p[50005], n, k ;

bool run(int m) {
    int cnt = 0, bef = -1 ; // 目前基地台數量、前一個基地台尾端(含)

    for (int i=0;i<n;i++) {
        if (cnt > k)        // 數量過多
            return false ;
        if (p[i] > bef) {   // 超出上一個基地台範圍
            bef = p[i] + m ; // 更新基地台範圍
            cnt++ ;           // 更新基地台數量
        }
        else
            continue ;
    }
    if (cnt > k) return false ; // 更新基地台數量
    return true ;
}


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

    cin >> n >> k ;

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

    sort(p, p+n) ; // 需排序才能進行

    int L = 1, R = p[n-1] ;

    while (L < R-1) { // 二分搜
        int m = (L+R) / 2 ;
        if (run(m)) // 能通過代表還能往前
            R = m ;
        else
            L = m ;
    }

    cout << R ;

    return 0 ;
}

經過這兩個例題，你應該已經掌握這種錢面對後面錯的技巧了
現在的問題就只剩下與二分搜搭配的函式怎麼寫，但是這並不是這次的主題
但是前面說過是看"單調性"，遞增遞減只是其中一部分而已
所以接下來要說說，如果遇到另外一種型態的題目該如何解決

## 一錯全錯的單調性
前面說過單調性可以簡單理解為遞增或遞減，但實際上並非這樣
假設有一個產品在流水線上需要經過 6 個正確的操作組成才能運作
並且每個操作結束後都會對半成品進行一次檢驗，檢測產品是否合格
不過所有的檢測機器出了點問題，現在不會攔截半成品，只會顯示是否合格
那麼如果第 4 個操作出了問題，理所當然檢測機器會顯示不合格
那之後的第 5、6 個操作呢，因為前面第 4 個操作錯誤的原因
不管這兩個操作是否合格，檢測機器都會顯示不合格
這就是所謂的"一錯全錯"，通常在題目中會去除或更換有問題的部分
由此來找出哪些操作是真正出現錯誤的，哪些又是被波及的
接下來就用例題去幫助各位進一步理解這個概念

### g598. 4. 真假子圖(2021/11)
這題的題目敘述比較難看懂，我在這裡重新梳理一下邏輯
簡單來說就是原本會將人分成兩組，但是目前只有部分人的名單
也就是說，有某些人是不能確定在哪一組的，而探員拿回來的名單
如果與前面已有的名單產生衝突就代表探員的名單是錯誤的
如果沒有產生衝突代表探員的名單是完全正確的
所以我們可以直接將探員的名單加入原有名單中
(ps 確保一定會有一個探員錯誤，最多三個探員錯誤)

那單調性要怎麼看出來呢，前面說過一錯全錯
假設有個探員把原本應該不同組的 A、B 分在同一組
那接下來的探員會延續這個概念，因為題目有說
被判斷為正確的名單會被加入原有名單中
現在如果把錯誤的探員視為正確的，把他的名單加入原有名單中
那麼後面的探員不論是否正確，最後都會出現錯誤結果
這就是這題的單調性，我們要不斷地找出第一個錯誤的探員並且刪除
最多刪除三次這題就結束了，因為最多只有三個錯誤探員

#include<bits/stdc++.h>
using namespace std ;
typedef pair<int, int> Pii ;
#define FF first
#define SS second

int n, m, p, k, col[20005] ;
vector<int> now[20005] ;
vector<Pii> e, v[10005] ;

bool dfs(int x, int pre) { // DFS
    for (int it: now[x]) { // 找所有可連接的邊
        if (it == pre) continue ; // 不走回頭路
        if (!col[it]) {
            col[it] = 3 - col[x] ; // 2 -> 1，1 -> 2
            if (!dfs(it, x)) return false ; // 找到錯誤
        }
        else if (col[it] == col[x]) return false ; // 找到錯誤
    }
    return true ;
}

bool check(int x) {
    // 先重置
    for (int i=1;i<=n;i++) {
        col[i] = 0 ;
        now[i].clear() ;
    }

    for (Pii it: e) {
        now[it.FF].push_back(it.SS) ;
        now[it.SS].push_back(it.FF) ;
    }

    for (int i=1;i<=x;i++) {
        for (Pii it: v[i]) {
            now[it.FF].push_back(it.SS) ;
            now[it.SS].push_back(it.FF) ;
        }
    }

    for (int i=1;i<=n;i++) { // 找錯誤
        if (!col[i]) {
            col[i] = 1 ;
            if (!dfs(i, 0)) return false ; // 找到錯誤了
        }
    }
    return true ;
}

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

    cin >> n >> m ;
    int x, y ;
    for (int i=0;i<m;i++) {
        cin >> x >> y ;
        e.push_back({x+1, y+1}) ;
    }

    cin >> p >> k ;

    for (int i=1;i<=p;i++) { // 新增邊
        for (int j=0;j<k;j++) {
            cin >> x >> y ;
            v[i].push_back({x+1, y+1}) ;
        }
    }

    int L = 0, R = p ;
    for (int i=0;i<3;i++) { // 三個錯誤探員
        while (R-L > 1) {  // 二分搜
            int mid = (L+R) / 2 ;
            if (check(mid)) L = mid ;
            else R = mid ;
        }
        cout << R << '\n' ;

        v[R].clear() ;
        L = R ;
        R = p ;
        if (check(p)) break ;
    }

    return 0 ;
}

這題我沒有詳細講的原因是這個時間複雜度太差了(雖然還是能過)
主要是想告訴各位第二種單調性的呈現，而不是只有遞增遞減
建議還是使用 DSU 的解法會比較好，我個人認為教育價值也比較高

## 其他題目
對於其他 APCS 的題目，我都放在這裡並提供程式碼，但是不會多做解釋

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

int n, k ;
vector<int> high, width ;

bool check(int m) {
    int cnt = 0, idx = 0 ;
    // cnt 目前寬度、目前處理第 idx 個海報

    for (int i: high) {
        if (idx == k) break ; // 貼完所有海報
        if (i >= m) cnt++ ; // 比 m 高就能貼海報
        else {
            cnt = 0 ; // 貼海報可能破碎
            continue ;
        }
        if (cnt == width[idx]) { // 可以貼的海報+1
            idx++ ; // 處理下一張海報
            cnt = 0 ;
        }
    }

    return idx == k ;
}

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

    int L = -1, R = 0 ;
    cin >> n >> k ;
    high.resize(n), width.resize(k) ;

    for (int i=0;i<n;i++) {
        cin >> high[i] ;
        if (R <= high[i])
            R = high[i]+1 ;
    }

    for (int i=0;i<k;i++)
        cin >> width[i] ;

    while (R-L > 1) { // 二分搜
        int m = (R+L) / 2 ;
        if (check(m)) // 通過
            L = m ;
        else
            R = m ;
    }

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