三分查找适用于单峰函数，即先单调增后单调减（上凸）或先减后增（下凸）的连续函数，如二次函数 -x²+4x、绝对值和函数等；必须人工保证区间内单峰性，否则结果错误。
三分查找适用的凸函数长什么样
三分查找只适用于严格单峰函数，也就是先单调增再单调减（上凸）或先减后增（下凸）的连续函数。C++ 中没法自动判断函数是否凸，必须由你保证 f(x) 在给定区间 [l, r] 上是单峰的——否则结果不可靠，甚至完全错误。
常见可直接用三分的场景：二次函数（如 -x*x + 4*x）、带绝对值的和（如 abs(x-1) + abs(x-3) + abs(x-5)）、某些几何距离和、简单多项式拟合目标函数。
容易踩的坑：
• 把非单峰函数（比如有多个局部极值的 sin(x) + 0.1*x 在大区间上）硬套三分，结果停在某个局部极值点
• 区间端点选得太大，导致浮点精度丢失或迭代不收敛
• 忘记检查函数定义域，f(x) 在中间某点崩溃（如除零、越界访问）
标准三分模板怎么写（double 精度版）
核心逻辑是不断缩小区间，保留包含极值的那一段。对上凸函数（求最大值），保留 f(m1) 的那一侧；下凸函数（求最小值）则反过来。实际中多数人直接按「求最大值」写，需要最小值时把目标函数取负即可。
double ternary_search(double l, double r, int iter = 100) {
while (iter--) {
double m1 = l + (r - l) / 3.0;
double m2 = r - (r - l) / 3.0;
if (f(m1) < f(m2)) {
l = m1;
} else {
r = m2;
}
}
return (l + r) / 2.0;
}说明：
• 迭代次数 iter = 100 比固定精度（如 r-l ）更稳，避免浮点震荡<br>
• <code>m1 和 m2 必须严格在 (l, r) 内，不能写成 l + (r-l)/2 或错位计算
• 函数 f 必须是捕获上下文的 lambda 或全局/静态函数，不能带未绑定的 this 指针（类成员函数需包装）
整数域三分要注意什么
当自变量必须是整数（比如数组下标、离散决策点），不能直接用浮点三分。此时要改用整数三分，终止条件是 r - l ，最后暴力检查剩余 2–3 个点。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
int ternary_search_int(int l, int r) {
while (r - l > 2) {
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
if (f(m1) < f(m2)) {
l = m1;
} else {
r = m2;
}
}
int res = l;
for (int i = l; i <= r; ++i) {
if (f(i) > f(res)) res = i;
}
return res;
}关键点：
• m1 和 m2 用整数除法，但要确保 m1 （当 <code>r-l 时可能相等，所以必须加循环终止条件）<br>
• 不要试图用 <code>while (l + 四舍五入逼近，整数三分没有“中间点唯一性”，必须收尾暴力<br>
• 如果函数在整数点不满足严格单峰（比如平台段），三分只能返回其中一个极值位置，无法区分多个解
为什么不用 std::max_element 或二分
二分只适用于单调函数，遇到单峰就失效；而 std::max_element 时间复杂度是 O(n)，三分是 O(log n) —— 当 f(x) 计算代价高（比如每次调用含一次 Dijkstra 或矩阵乘），或者定义域极大（1e18 范围）时，三分优势明显。
但要注意：
• C++ 标准库没有内置三分，必须手写
• 如果函数计算非常快且定义域小（比如 n ≤ 1e5），线性扫反而更稳、更易 debug
• 浮点三分中，若 f 本身有噪声（比如涉及随机数或数值积分误差），f(m1) == f(m2) 可能频繁出现，建议加微小扰动或改用黄金分割搜索
最常被忽略的是：三分只返回一个极值点横坐标，不告诉你这是最大值还是最小值——你得自己根据函数趋势或额外采样判断。
