# 三分搜尋法 Ternary Search
三分搜尋法基本上不常用，但是每次用到時都會令人驚艷 ||~~(驚嚇)~~||

## 為什麼需要用到三分搜尋法
我們在[二分搜尋法](https://hackmd.io/@ShanC/binary-search)學過如何尋找具有單調性的資料。然而，當資料不具有單調性，我們勢必需要換一種方法來搜尋

### 單調性
單調性就是對於一個函數 $f(x)$: 「當 $x$ 越大 $f(x)$ 也會越大」 或者 「當 $x$ 越大 $f(x)$ 也會越小」

<img src="https://res.cloudinary.com/bend/f_auto/shikakutimes/s3/bend-image/1645534943.png" style="margin: 0 auto; display: block; width: 400px">

<p class="text-center">圖源: <a href="https://manabitimes.jp/math/1289">https://manabitimes.jp/math/1289</a></p>

簡單來說，整個函數是「遞增」或是「遞減」，不會有兩種同時出現的狀況。這個性質是二分搜尋法必須遵守的規定

### 二分搜尋法的問題
由於二分搜尋是基於對於整個函數全部都是遞增或是全部都遞減。然而，假設有一個**曲線函數**，此函數有明確的**極值**作為頂點，那麼在頂點的位置方向性會產生變化，我們無法用二分搜尋法找出理想的答案

<img src="https://hackmd.io/_uploads/Sy3hFaEDyg.png" style="margin: 0 auto; display: block; width: 400px">

<p class="text-center">
上圖極點左邊是遞減，右邊是遞增
</p>

### 微分?
學過基礎微積分的大家，應該會知道這種情況最好的工具就是微分求斜率的函數，對於一連續函數 $f(x)$，只要找到 $f'(x) = 0$ 就能找出答。然而，我們拿到的資料時常是離散的。其次，如果不是單純的二次函數 (如上圖)，也難以找出答案

## 三分搜尋法 Ternary Search
### 介紹
三分搜尋法主要常用在「逼近」答案，不見得是算出明確的數值。主要流程如下:

維護兩個變數 $l, r$ 代表左與右邊界，在另外維護兩個邊界 $ml, mr$ 代表左右分割點，其中 $ml = l + \cfrac{(r - l)}{3}, ~mr = r - \cfrac{(r - l)}{3}$

可以將 $ml, mr$ 帶入 $f(x)$ ，如果發現 $f(ml) < f(mr)$，則說明 $ml$ 更接近極點

<img src="https://hackmd.io/_uploads/H1AJkANwJe.png" style="margin: 0 auto; display: block; width: 400px">

$~$
如果發現 $ml$ 較靠近極點，則移動右邊界 $r$ 至右分割點 $mr$，原本的區間 $[mr, r]$ 就無視掉。反之則將左邊界 $l$ 移至左分割點 $ml$，無視掉區間 $[l, ml]$。接下來重新計算 $ml, mr$

<img src="https://hackmd.io/_uploads/SkefBRNDJg.png" style="margin: 0 auto; display: block; width: 400px">

$~$
重新以上步驟直到 $l = r$，或著如果數字除不盡，多重複幾次，就可以找到答案或近似解

### 程式碼實作

double l = 0, r = 1e6; // 視資料改資料型態
while(l < r){
    double ml = l + (r - l) / 3.0;
    double mr = r - (r - l) / 3.0;
    
    if(f(ml) < f(mr))
        r = mr;
    else
        l = ml;
}
cout << (l + r) / 2.0 << '\n'; // 輸出答案 x
cout << f((l + r) / 2.0) << '\n'; // 輸出極值 f(x)

理論上 $\frac{(l + r)} {2}$ 會更接近答案，但是如果 `while` 迴圈跌代夠多次，其實 $l$ 或是 $r$ 都可以是答案

三分搜尋法的程式碼其實都差不多，問題僅在於 $f(x)$ 要如何定義。換句話說，難點在於如何觀察出曲線函數 $f(x)$

### 時間複雜度
根據 Master theorem:
$T(n) = T(2n/3) + O(1)=O(log~n)$

## 例題說明
來源: [Online Judge 10041 - Vito's Family](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982) (這個網站很常當機)
如果不行換這個: [Vjudge Vito's Family](https://vjudge.net/problem/UVA-10041)
如果再不行就換這個: [Zerojudge a737. 10041 - Vito's family](https://zerojudge.tw/ShowProblem?problemid=a737)

### 題目
已知一條路上有 $r$ 棟房子，分別位於 $s_1, s_2, ..., s_r$。希望能寫出一個程式找到一棟房子使得其與其他房子的距離之和能夠最小

### 限制
- $0 < r < 500$
- $0 < s_i <30000$

### 題解
我們不知道是哪一間房子能求出最小值，因此可以自己把數字帶進去試試看，當靠近邊界的房子代進去的時候會是很大的值，逐漸靠近答案時會越來越小。不難發現，他其實就是一個**具有極值的曲線函數**，因此三分搜尋就可以找出答案。其中，$f(x)$ 的定義如下:

$f(x) = \sum_{i=1}^{r} |s_i - x|$

### 程式實作

#include <iostream>
using namespace std;

const int MAXN = 505;
int n, arr[MAXN];

int cost(int tar) { // f(x)
    int ret = 0;
    for (int i = 0; i < n; i++)
        ret += abs(tar - arr[i]);
    return ret;
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        
        // 以下為三分搜尋的模板
        int l = 0, r = 30000, t = 25;
        while (t--) { // 根據測試，25~100 次跌代都可以找到答案
            int ml = l + (r - l) / 3;
            int mr = r - (r - l) / 3;
            if (cost(ml) < cost(mr))
                r = mr;
            else
                l = ml;
        }

        cout << cost((l + r) / 2) << '\n';
    }

    return 0;
}

### 為什麼跌代 25 次就能得到解答
已知邊界介於 $[0, 30000]$，每次線段分割成原本長度的 $\frac{2}{3}$ ，因此只要跌代 $log_{\frac{3}{2}}(30000) \approx 25$ 就可以求出解答

也因此，此程式碼每筆測資的複雜度是 $25\times O(n)=O(n)$

## 性質: 中位數最小化絕對偏差的和
其實，上述的例題 [Vito's Family](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982) 在網路上，大家都是去找中位數來求出解答，然而我們卻是使用逼近的方法找的，其實用直覺不難觀察出來「中位數可以找到此題的解」這個結論。但這其實是可以證的，以下證明:

### 命題: 中位數最小化絕對偏差的和
設一個集合 $S$ 有 $n$ 個元素，其中 $s_1<s_2<...<s_n$，則 $\sum_{s\in S} |s - x|$ 在 $x$ 是 $S$ 的中位數時，有最小值

### 證明
令 $f(x)=\sum_{s\in S} |s - x|$

如果 $x < s_1$，則 $f(x)=\sum_{s\in S} |s - x| = \sum_{s\in S} (s - x)= \sum_{i=1}^{n} (s_i - x)$

當 $x$ 變大的時候 $f(x)$ 會變小直到 $x$ 碰到 $s_1$，因此對於所有 $x < s_1$， $f(s_1)<f(x)$

現在我們假設 $s_k \leq x \leq x+d\leq s_{k+1}$，$d$ 是否個很小的數，則

$\begin{split}
f(x+d) &= \sum_{i=1}^{k}(x+d-s_i)+\sum_{i=k+1}^{n}(s_i-(x+d))
\\&= dk+\sum_{i=1}^{k}(x-s_i)-d(n-k)+\sum_{i=k+1}^{n}(s_i-x)
\\&= d(2k-n)+\sum_{i=1}^{k}(x-s_i)+\sum_{i=k+1}^{n}(s_i-x)
\\&= d(2k-n)+f(x)
\end{split}$

所以 $f(x+d)-f(x)=d(2k-n)$
而這說明，當 $2k<n$ 時是負值；當 $2k=n$ 時是 $0$；當 $2k>n$ 時是正值，因此在區間 $[s_k, s_{k+1}]$ 中:

$f(x)$ 是 $\begin{cases} 遞減, ~如果 ~2k<n\\常數, ~如果 ~2k=n\\遞增, ~如果 ~2k>n\\ \end{cases}$

因此可以知道，當我們把 $s_k = s_\frac{n}{2}$ (即中位數) 代入 $x$ 時，有極小值

### 另解 Vito's Family
藉由上面的微分證明，可以得知使用中位數也可以得到相同的解答。回到例題 [Vito's Family](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982)，我們可以先排序，再找出中位數

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

int main(){
    int t, n;
    cin >> t;
    
    while(t--){ // 迴圈 t 次
        cin >> n;
        vector<int> vec(n);
        for(int &i : vec) // 把在 vec 上的東西 (位置) 都列出來
            cin >> i;
        
        // 先排序再找出中位數
        sort(vec.begin(), vec.end());
        int mid = vec[n / 2], ans = 0; 
        
        for(int &i : vec)
            ans += abs(mid - i); // 算出距離總和
        
        cout << ans << '\n'; // 輸出答案
    }
    return 0;
}

## 題目練習
因為三分搜可以逼近答案，因此適合在需要算小數或是計算幾何的題目出現
有時候如果想不出可以用什麼演算法，也可以用用看三分搜去搜尋答案

[CSES Stick Lengths](https://www.cses.fi/problemset/task/1074) (差不多就是 Vito's Family 那一題，找中位數即可)
[Zerojudge d452. 二、直線最小距離和](https://zerojudge.tw/ShowProblem?problemid=d452) (就是 Vito's Family，找中位數即可)
[Zerojudge f990. 距離](https://zerojudge.tw/ShowProblem?problemid=f990) (用三分搜尋逼近答案)
[Codeforces - Weakness and Poorness](https://codeforces.com/problemset/problem/578/C) (把題目看懂 + 三分搜逼近)
[Codeforces - Restorer Distance](https://codeforces.com/problemset/problem/1355/E)
[Online Judge 13010 - Galactic taxes](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4898) (最短路徑 + 三分搜逼近答案)

----

## 參考資料
- [cp-algorithms - Ternary Search](https://cp-algorithms.com/num_methods/ternary_search.html)
- [海大競程 - search algorithm & 實作misc](https://hackmd.io/@LeeShoWhaodian/Byyg2J6byl#/)
- [geeksforgeeks - Ternary Search](https://www.geeksforgeeks.org/ternary-search/)
- [The median minimizes the sum of absolute deviations (the ℓ1 norm)](https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations-the-ell-1-norm)
- [培哥 -【題解】CPE 一顆星選集：1. Vito’s Family](https://andyli.tw/cpe49-1/)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/1/16