進階二分搜
二分搜
- 單調
- 遞增
通常來說，複雜度
單調性 \(\geq\) 遞增
遞增本身也是單調性的一種展現 
不過他有更多的好性質，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 )\)
通常可以使用\(lower\_ bound\)之類的函式去完成
\(O(lg C \times T(N) )\)
透過搜尋值域丟進演算法\(T\)裡面
\(O(T(N) \times(lg C \times N) )\)
只是提供一個想法，我好像還沒有遇過
二分搜小技巧
int m = (l+r)/2;
int m = (l+r)>>1;
常數優化
int m = (l+r)>>1;
int m = l + ((r-l)>>1);
可以避免爆值域( 如果你不想用 __int128 的話 )
int m = (l+r)>>1;
int m = (l+r+1)>>1;
主要是體現在\(r-l = 2\)的時候
二分搜延伸
- 三分搜
- 整體二分搜
- candle (推薦 毒瘤 )
treap
進階二分搜
{"metaMigratedAt":"2023-06-17T11:44:22.661Z","metaMigratedFrom":"YAML","title":"進階二分搜","breaks":true,"contributors":"[{\"id\":\"4c53837e-3941-4548-b5f6-035c3cd0eb0f\",\"add\":1383,\"del\":29}]"}