题目
有序数组为[1,3,3,3,7]，要求返回第一个等于3的下标。二分过程中mid位置的值等于3时，下一步应（）。
题目类型：原创高频练习题
用途：用于帮助理解程序员相关考点和答案解析，不等同于官方真题。
正确答案
C
普通二分找到任意一个3即可返回，但左边界问题还要排除左侧存在相同值。命中后保留候选位置并令右边界左移，直到搜索区间结束。
选项分析
A
错误。可能返回下标2或3，而不是最左下标1。
B
错误。目标是更左位置，命中后不应只往右。
C
正确。记录答案并继续压缩右边界。
D
错误。破坏有序性会丢失二分查找条件。
本题为什么容易错
许多代码模板能找到一个目标值，却没有写清要找哪一个。题目一旦出现第一个、最后一个、插入位置，命中后的动作就变了。
先看结论
简短答案
有序数组中存在多个3，二分查找怎样找到最左边的3，正确答案是 C（记录mid为候选答案，并继续收缩右边界到左半区寻找更早的3）。普通二分找到任意一个3即可返回，但左边界问题还要排除左侧存在相同值。命中后保留候选位置并令右边界左移，直到搜索区间结束。
解析
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 立即返回mid，不再检查左侧 | 本题干扰项 | 错误。可能返回下标2或3，而不是最左下标1。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 只向右半区查找 | 本题干扰项 | 错误。目标是更左位置，命中后不应只往右。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 记录mid为候选答案，并继续收缩右边界到左半区寻找更早的3 | 本题正确答案 | 正确。记录答案并继续压缩右边界。 | 看到题干核心场景时优先联想到它 |
| 把数组改成无序后重新遍历 | 本题干扰项 | 错误。破坏有序性会丢失二分查找条件。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 立即返回mid，不再检查左侧：错误。可能返回下标2或3，而不是最左下标1。
- 只向右半区查找：错误。目标是更左位置，命中后不应只往右。
- 把数组改成无序后重新遍历：错误。破坏有序性会丢失二分查找条件。
复习
知识点详解
一种实现是在值等于target时记录mid并令right=mid-1；另一种是寻找第一个不小于target的位置，循环结束后检查该位置是否越界且值等于target。
备考速记
命中只是找到一个；要找第一个，记下来还得继续往左。
lower_bound 在有序数组场景中的作用
数组[1,3,3,3,7]中，普通二分第一次可能命中下标2；左边界算法继续检查左侧，最后返回下标1。
拓展
同类题怎么考
- 在重复元素数组中寻找第一个目标值。
- 根据lower_bound结果判断目标是否存在。
lower_bound 在程序员软考中的考法
看到‘第一个’就不能命中即停。检查代码是否保留候选并继续向左收缩，是最快判断方法。
解题思路
命中只证明‘这里有3’，没有证明‘这里是第一个3’。要继续往左查，若再命中就更新候选，最终留下最左位置，选C。
考点定位
找任意值、找第一个等于、找第一个不小于是三个不同契约。边界更新必须跟函数契约一致。
易错提醒
- 命中立即返回，重复值时结果不稳定。
- 使用闭区间循环却按半开区间更新边界，造成死循环。
- 搜索结束后未验证候选位置确实等于target。
备考提示
- 先用一句话写清搜索契约，再选择边界模板。
- 在书木兰软考题库 https://www.shumulan.com/ 练二分题时，可把‘任意命中、左边界、右边界、插入位置’分别放进错题标签。
你可能还想了解
- 二分查找如何找到第一个3？
- 命中target后为什么不能立即返回？
- lower_bound和普通二分有什么区别？
本文小结
寻找第一个等于目标值的位置时，命中mid后要记录候选并继续向左收缩，不能像普通二分一样立即返回。