# 二分搜與對答案二分搜

對答案二分搜是個針對模擬問題的一種優化方式，在結果的上下界容易求出，並且結果具有單調性，就能利用二分搜來進行優化。
## 二分搜
>給定一升序排序過的整數陣列，大小為n，給定一整數d，求陣列中第一個$\geq n$的數字的index。

首先第一個最直接的想法，就是直接將整個陣列掃描一遍，直到找到第一個$\geq n$的數字即可。然而這樣的演算法效率較差，複雜度為$O(n)$。

再次觀察題目，會發現我們沒有充分利用陣列是升序排序過的性質。如果在一個位置的數字小dn，那在其左邊的位置皆不可能是答案，同樣地，如果一個數字大於等於d，那答案一定不會在它的右邊。利用這個性質，我們可以每次都從要搜尋的區間檢查其最中間的數字，然後用結果來更新搜尋區間的左右界。由於每次搜尋區間都會被切一半，複雜度為$O(logn)$，大幅度地優化了演算法。

面對二分搜的問題，首先要做的就是先找出「單調性」，也就是在某種比較大小的定義下滿足遞增或遞減(未必是數字上的大小，例如std::pair的比較)，再去利用上下界來二分搜。

有關單調性的更詳細說明，請參考[wiwiho大佬的筆記](https://hackmd.io/@wiwiho/CPN-monotone-and-order)

以下是有關二分搜的題目：
[CF 706B](https://codeforces.com/problemset/problem/706/B/)
[TIOJ 1044](https://tioj.ck.tp.edu.tw/problems/1044)
[TOI2021入營考pC](https://hackmd.io/@SorahISA/toi2021)(LIS的$O(nlogn)$實作 )

## 對答案二分搜

>APCS2017P3
>給定在+x軸整數點的n個位置，求最小的區間大小使得K個區間能覆蓋所有n個整數點

由於點的位置跟分散程度都未知，似乎沒有一個快速的解法，只能利用模擬來求解。首先，答案不需要求出區間的位置，因此我們只需要找到最小的區間大小即可。

最直覺的想法是將區間大小由1慢慢增加並驗證，並且因為區間的放置可以貪婪地將左界放在第一個未覆蓋的點上，驗證可以在O(n)做完。然而，逐一遞增區間大小效率非常差，如果最左與最右的點位置相差d，時間複雜度為$O(dn)$，因此我們需要優化它。

觀察題目，會發現如果答案為X，那區間大小$\geq X$的情況一定能覆蓋，區間大小$< X$的一定不能完全覆蓋，發現了單調性的存在，似乎可以做二分搜，上下界分別為$\lceil \frac{d}{K} \rceil$和1，那麼我們就可以對區間大小做二分搜，達到$O(nlogd)$的好複雜度。

總結來說，對答案二分搜是利用答案與某個變數的單調性(例如大於等於答案就可做，小於則不行)，來減少模擬的情況。

以下是對答案二分搜的一些題目：
[APCS200704P3](https://zerojudge.tw/ShowProblem?problemid=f581)
[TOI2021入營考pB](https://hackmd.io/@SorahISA/toi2021)

## 參考資料
https://hackmd.io/@gilbert33/r1MIpp0Fv?print-pdf#/
https://hackmd.io/@wiwiho/CPN-monotone-and-order
https://hackmd.io/@SorahISA/toi2021