二分
355 字
2 分钟
二分
二分算法
-
解集具“二段性”即可用：前一段不满足，后一段一定满足，或反之
-
两套模板
- 找左端点，满足条件的最小下标（≥x 的最小元素）
int l = 1, r = n;while (l < r) { int mid = l + (r - l) / 2; // 防溢出 if (check(mid)) r = mid; // 条件真，答案≤mid else l = mid + 1; // 条件假，答案>mid}// 结束时 l==r，再验证 a[l] 是否真满足2.找右端点，满足条件的最大下标（≤y 的最大元素）
int l = 1, r = n;while (l < r) { int mid = l + (r - l + 1) / 2; // 向上取整 if (check(mid)) l = mid; // 条件真，答案≥mid else r = mid - 1; // 条件假，答案<mid}- STL
#include <algorithm>vector<int> a;auto it1 = lower_bound(a.begin(), a.end(), x); // ≥x 最小元素auto it2 = upper_bound(a.begin(), a.end(), x); // >x 最小元素// 返回迭代器，解引用 *it，下标 it - a.begin()。// 想拿 ≤x 的最大元素：--it2（先判 it2!=a.begin()）时间复杂度
O（log n）
二分答案
- 最大值最小/最小值最大
bool check(int mid) { /* 判定“答案≤mid”是否可行 */ }
int left = MINAns, right = MAXAns;while (left < right) { int mid = left + (right - left) / 2; // 左端点版 if (check(mid)) right = mid; // 可行，尝试更小 else left = mid + 1; // 不可行，需更大}// left 即为“最小化最大值”时空复杂度
O（log n）
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
算法错题本
算法在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
2
数论
算法如果 $a$ 除以 $b$ 没有余数，那么 $a$ 就是 $b$ 的倍数，$b$ 就是 $a$ 的约数，记作 $b \mid a$。 约数，也称因数。
3
高精度
算法当数据的值特别大，超出各种基本数据类型的存储范围时，需要使用高精度算法来计算加减乘除。
4
分治
算法问题一分为二 —递归(DFS)-合并答案 时间优化：O(nn)-O(n log n)
5
贪心
算法思路 猜一个排序依据（比如按重量、按 deadline、按权值差等） 任取相邻两项 i, j 假设顺序错了，写出交换前/后只与这两头有关的代价/收益表达式 令“交换后更优”得不等式，化简成key(i) key(j)这个 key 就是 so…
随机文章随机推荐