算法笔记

学习者：林悦

主题：有序数组中的二分查找

编程语言：Python 3

记录日期：0000-00-00

学习状态：已实现，边界复习中

一、问题定义与算法目标

给定一个按非递减顺序排列的整数数组，以及目标整数target，返回一个目标值所在下标；若目标值不存在，返回－1。本笔记采用闭区间二分查找，适用于能够按下标访问的有序数组。若数组中存在重复目标值，本实现返回其中一个位置；查找第一个或最后一个位置需要在命中后继续缩小区间，属于后续变式。

二、核心思路与区间约定

1. 使用left和right表示当前候选范围，两端均包含；初始值分别为0和数组长度减1，空数组对应right＝－1。
2. 每轮取中点mid。若中点值小于目标，排除中点及其左侧；若大于目标，排除中点及其右侧；相等则直接返回。
3. 循环条件为left≤right，保证只剩一个候选元素时仍会检查。每次未命中都会排除中点，候选范围严格缩小，最终命中或变为空区间。

三、实现代码

四、过程示例与复杂度

数组为［2，5，8，12，16，23］，目标为16。第一轮left＝0、right＝5、mid＝2，值8小于16，范围更新为［3，5］；第二轮mid＝4，值16等于目标，返回下标4。比较次数随候选范围逐步折半，最坏时间复杂度为O(log n)，额外空间复杂度为O(1)；这里的n为数组长度，复杂度描述针对非空规模的增长。

五、测试样例与边界记录

六、错误复盘与后续练习

初次实现使用left＜right，导致只剩一个元素时未检查；随后又把left更新为mid，在双元素场景中无法保证缩小范围。修订后统一采用闭区间、left≤right和排除中点的更新规则。林悦已手动推演空数组、单元素和两端命中三类边界，后续将用上述样例运行验证，再练习查找首个目标值的变式。

明晚先遮盖代码说明区间不变式，再独立实现并记录失败样例；三天后完成有序插入位置题，明确返回值含义和边界初始化。每个变式分别保存题目要求、区间约定及样例，避免把任一位置查找的终止条件直接套用到边界查找。