GESP 七级 · GESP 202412 C++ 七级 第 18 题

在 $n$ 个元素中进行二分查找，平均时间复杂度是 $O(\log n)$，但须要事先进行排序。

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

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

【考点】二分查找前提｜时间复杂度分析｜排序必要性

1. 🎯 考纲定位

GESP 七级编程基础模块，考查二分查找的前提条件与时间复杂度因果关系。命题人卡住的是那些只背"二分查找 O(log n)"结论、却从不追问"为什么是 log n"的考生——不理解有序性才是对数复杂度的根源。