GESP 八级 · GESP 202606 C++ 八级 第 12 题

某优化问题的答案是 $[1,M]$ 内的整数，存在单调判定函数 check(x)，且每次判定的时间复杂度为 $O(n)$。使用二分答案求最小可行值，整体时间复杂度通常为（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二分查找｜时间复杂度分析｜对数级迭代

1. 🎯 考纲定位

本题直击 GESP 八级核心考点：二分答案框架的综合复杂度计算。命题人卡住的是考生"会二分但算不清总复杂度"的弱点——八级前几题常考二分本身，到八级开始叠加函数调用开销，形成区分度。