题目重点：先确认定义域、函数调用成本和精度；整数凸函数保留可能的极小区间，实数凸函数按区间长度停止。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 文章代码是明确的训练变体：整数闭区间 [lo,hi] 上的单峰/离散凸函数，只能按整数 x 调用 f(x)，值有限；平局返回最小 x。
- 如果原题是连续实数凸函数，需要另问定义域与误差容限；若区间无界，先找括住极小点的范围。题目未明确这些条件。
解题路线
- 先问可否求导、定义域是否有限、一次函数调用成本以及误差要求。黑盒且有界时，三分选 m1、m2：若 f(m1)≤f(m2)，极小点可留在 [lo,m2]；否则留在 [m1,hi]。平坦区间时仍保留左侧以满足最小 x 约定。
- 整数实现避免两探针重合：当 hi−lo≤3 时停止缩区间，对剩余至多四个点枚举；用 cache 避免重复调用昂贵黑盒。
- 实数版在区间宽度≤epsilon 时停止，返回区间内候选并核误差；仅凭宽度只能保证位置误差，函数值误差还需连续性/Lipschitz 等约束。导数可得时，可二分导数变号；梯度下降需要步长与收敛条件，不能把它当未知黑盒凸函数的唯一答案。
手动走一遍
训练例 f(x)=(x−7)²、x∈[−20,20]，三分逐步保留包含 7 的区间，最终枚举返回 (7,0)。若 f(x)=|x−3|+|x−5|，最小平台是 x=3,4,5；训练 tie rule 返回 3。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training contract: minimize a discrete convex function on inclusive [lo, hi].
The source names an unknown convex function and ternary search, but gives no
domain, oracle signature, precision, or tie rule. This is one explicit variant.
"""
from collections.abc import Callable
def minimize_discrete_convex(
f: Callable[[int], float], lo: int, hi: int
) -> tuple[int, float]:
if lo > hi:
raise ValueError("empty search interval")
cache: dict[int, float] = {}
def value(x: int) -> float:
if x not in cache:
cache[x] = f(x)
return cache[x]
while hi - lo > 3:
third = (hi - lo) // 3
m1 = lo + third
m2 = hi - third
if value(m1) <= value(m2):
hi = m2
else:
lo = m1
best = min(range(lo, hi + 1), key=lambda x: (value(x), x))
return best, value(best)
if __name__ == "__main__":
assert minimize_discrete_convex(lambda x: (x - 7) ** 2, -20, 20) == (7, 0)
assert minimize_discrete_convex(lambda x: abs(x - 3) + abs(x - 5), 0, 10) == (3, 2)
复杂度
区间长度 N 每轮约缩为 2N/3，O(log N) 轮和黑盒调用；cache 空间 O(log N)，尾部常数枚举。连续版达到位置精度 epsilon 为 O(log((hi−lo)/epsilon)) 次调用，但数值精度仍由函数性质决定。
易错点与追问
容易失分的边界
- 没有有限区间就直接三分。
- 整数 m1=m2 时死循环。
- 把单峰/凸函数当任意多峰函数缩区间。
- 只给位置误差却宣称函数值误差。
- 平局时任意丢弃整段极小平台，违背明确的 tie rule。
继续深挖
- 定义域是实数且函数不光滑，停止条件怎么定？
- 黑盒调用非常昂贵时怎样缓存与批量化？
- 如果函数是多峰的，三分哪里会失效？
- 导数可用时二分导数与三分函数值怎样比较？
