我從以前到現在都不太擅長二分搜相關的題目。
有人可能會想：
「二分搜不就是一直往中間找嗎？有什麼難的？」
實際開始寫題目後，才會發現二分搜的題目不知道要搜尋什麼，甚至看不出來題目是二分搜。
大部分二分搜的題目，很多時候根本沒有實際的陣列可以搜尋。
而是要用到 Greedy Algorithm 先把 check() 寫出來，再對超大範圍的答案做搜尋。
這篇主要是整理我自己一路以來對二分搜尋的綜整理解。
簡單粗暴的理解二分搜尋
這邊就不對簡單的二分搜尋基本概念作講解了，直接進入正文。
對陣列進行二分搜尋
一般提到二分搜，都是像這樣去陣列裡面找：
但大部分會出現二分搜的題目，通常都不是在「已經給定的陣列」裡面搜尋。
而是直接給你一個巨大的答案範圍，然後詢問類似這樣的問題：
- 最小的最大值
- 至少需要多少
- 最大可以到多少
這種需要在大範圍答案中，找出符合條件的極值的問題。
不太可能真的去創建及遍歷一個大小可能為 $10^9$ 的陣列，一般會直接用「對答案二分搜」來解答。
對答案進行二分搜尋
我們可以用非常非常簡單的問題來舉例：
在
1~100這個範圍內，尋找小於45的最大數字。
將條件寫成 check() 函式
我們可以將 檢查數字是否 < 45 寫成一個名為 check 的 bool 函式：
bool check(int val){
return val < 45;
}
只要 check() 回傳 ture 就代表 數字 < 45。
假設透過 check() 將整個範圍的數字進行判斷，會出現像是這樣的圖：
這時候會發現整個陣列，被切成了 符合條件 與 不符合條件 兩個區域。
這就符合了二分搜所需的單調性(Monotonicity)，因此可以直接對這個範圍進行二分搜。
初始化左右邊界與中間值
首先設定名為 L 與 R 作為邊界值，並分別給予 1 和 100 的初始值
int L = 1, R = 100;
設定二分搜的中間值 Mid，並初始化為 L 與 R 的中間值。
int Mid = L + (R - L) / 2;
提示盡量不要直接寫
(L + R) / 2。當L與R很大時，可能會造成溢位。
模擬二分搜尋的過程
將 Mid 傳入 check()，試著模擬二分搜的過程：
check(Mid) = false。代表Mid太靠右，將R = Mid以此收窄右邊範圍。
check(Mid) = true。代表Mid太靠左，將L = Mid以此收窄左邊範圍。
check(Mid) = true。繼續收窄範圍。
收斂到答案
一直循環往復直到 L + 1 == R，邊界 L 與 R 完全收窄：
此時：
L就是 符合條件的最大值R就是 不符合條件的最小值
因此答案就是目前的 L，也就是 44。
我們可以將上述的過程撰寫成程式碼：
pair<int, int> binarySearch(int L, int R){
while (L + 1 < R) {
int Mid = L + (R - L) / 2;
if (check(Mid))
L = Mid;
else
R = Mid;
}
return {L, R};
}
額外擴展邊界？
不過這個程式碼還有一點問題。
一開始定義：
L一開始一定要是trueR一開始一定要是false
當全部數字都符合條件或是全都不符合條件時，會導致最後算出的 L 和 R 是錯誤的。
因此可以在二分搜一開始直接擴展邊界一格：
--L, ++R;
就可以避開這個問題。
二分搜尋模板
若將 binarySearch() 加上 C++ 的泛型，並將 check() 改成使用 Lambda 撰寫並傳入。
則可以寫出十分簡單易記的二分搜萬用模板：
template <typename T, typename FuncT>
pair<T, T> binarySearch(T L, T R, FuncT check){
--L, ++R;
while (L + 1 < R) {
T Mid = L + (R - L) / 2;
if (check(Mid))
L = Mid;
else
R = Mid;
}
//L:符合條件的最大值 R:不符合條件的最小值
return {L, R};
}
第一次寫程式相關的教學文，若有沒講清楚或是需修改的地方可以用剛剛加入的評論區~