# 進階二分搜 --- # 二分搜 --- - 單調 - 遞增 ---- 通常來說，複雜度 單調性 $\geq$ 遞增 ---- 遞增本身也是單調性的一種展現 :poop: 不過他有更多的好性質，ex: 可以用雙指針維護 --- # 製造單調性or遞增性 如果題目跟順序無關的話可以考慮$sort$ 如果是前綴和有單調性的話可能就考慮**離線**or**線段樹** --- # 二分搜小應用 離散化 --- # 時機 ---- $設T(N)為執行一向演算法g的複雜度、C為值域$ - $O(T(N) \times lg C)$ - $O(lg C \times T(N) )$ - $O(T(N) \times(lg C \times N) )$ 這些有什麼區別? ---- $O(T(N) \times lg C )$ [兩數之和](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a672) [LIS](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a628) [Nested Ranges Check](https://cses.fi/problemset/task/2168/) ---- 通常可以使用$lower\_ bound$之類的函式去完成 ---- $O(lg C \times T(N) )$ 透過搜尋值域丟進演算法$T$裡面 ---- [111第一次學科能力競賽第五題](https://codeforces.com/gym/400758/problem/1E) [a080](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a080) ---- $O(T(N) \times(lg C \times N) )$ 只是提供一個想法，我好像還沒有遇過 :poop: --- # 二分搜小技巧 ```cpp= int m = (l+r)/2; ``` ```cpp= int m = (l+r)>>1; ``` ---- 常數優化 :poop: ---- ```cpp= int m = (l+r)>>1; ``` ```cpp= int m = l + ((r-l)>>1); ``` ---- 可以避免爆值域( 如果你不想用 \_\_int128 的話 ) ---- ```cpp= int m = (l+r)>>1; ``` ```cpp= int m = (l+r+1)>>1; ``` ---- 主要是體現在$r-l = 2$的時候 --- # 二分搜延伸 - 三分搜 - 整體二分搜 - [candle](https://csacademy.com/contest/archive/task/candles/statement/) (推薦 毒瘤 :poop: ) <del>treap</del>