每次循环先校验首尾元素的二分查找实现执行效率是否更高？

你的判断不正确，该实现在绝大多数场景下执行时间比标准二分查找更长，仅在目标大概率落在区间首尾的极特殊场景下可能有收益。

核心原因 #

• 每轮循环额外开销更大：该实现比标准二分查找每轮循环多了2次数组内存访问、2次相等比较操作。内存访问的耗时远高于算术运算，在目标没有命中区间首尾的绝大多数场景下，额外增加的开销完全覆盖了可能减少的循环次数带来的收益，整体执行时间反而更高。
• 优化触发概率极低：只有当目标刚好落在当前搜索区间的首尾时，该优化才能减少循环次数。对于随机分布的查找目标，该命中概率仅为2/区间长度，数组长度越大概率越低，在常用的大数据量二分查找场景下几乎无法触发，优化收益可以忽略。
• 最坏场景耗时更高：两种实现的时间复杂度均为O(logn)，但当目标不存在、或者目标位于数组中间位置时，该实现每轮都要执行额外的首尾判断操作，整体耗时比标准二分查找更高。

你提供的代码存在的语法/逻辑问题 #

• 变量n未初始化就使用：你定义int n;后没有对其赋值，就直接用于sort(v.begin(),v.begin()+n)和last = n-1计算，属于C++未定义行为，运行结果不可控。
• 不符合C语法规范：main函数未声明返回值为int，不符合C标准要求。

内容的提问来源于stack exchange，提问作者STEV