算法契约、不变量与反例

二分查找、线性结构与循环不变量

前置：能阅读整数数组、比较操作与循环，理解半开区间 [lo,hi)；Python 3.10+ 仅供手推或自跑完整下界程序。教学范围为比较模型；Python 3.10+；半开区间。核对日期2026-10-17。示例未执行，本轮没有安装依赖、生成协议代码、启动服务或浏览器预览。完整文件与输入见下界程序、输入与逐步练习；推演结论只适用于写明的模型。

二分查找输入契约

二分查找输入契约要求有序数组按同一比较规则排列。下界是第一个不小于目标的下标，目标不存在时也能返回插入点；查找相等元素还须检查下标小于长度。一次查询先排序会花费更多工作，不能只报告查找环节。

数组与链表的选择

数组与链表的选择取决于操作序列。随机访问适合连续数组；在数组中间插入要移动后缀。链表只有持有节点时才能常数时间插入，先按下标寻找仍需线性时间，还付出指针与分配开销。

二分循环不变量

对 [1,3,3,8] 求目标 3 的下界，最初 [lo,hi)=[0,4)。mid=2 时值为 3，把 hi 收到 2；mid=1 时仍为 3，再收至 1；mid=0 时值为 1，把 lo 推到 1。左右边界汇合后，左边全小于 3，右边全不小于 3，所以位置 1 正是最左合法插入点。

查看图表代码

二分循环不变量把位置分为三段：左侧所有值小于目标，右侧所有值不小于目标，中间半开区间尚待判断。初始两侧为空；遇到小值令lo=mid+1，否则令hi=mid，两个已知区域都保持成立。

来源与适用边界

• 英文官方、作者或规范原文：本专题机制依据；按上述固定版本族阅读。
• 中文官方或作者资料：用于术语和讲解交叉核对，冲突以原始规范为准。

二分终止、复杂度与最短路边界

二分为什么终止

用只剩一个元素的区间 [2,3) 检查更新：mid=2，若值小于目标，lo=mid+1=3；否则 hi=mid=2。两条分支都使长度从 1 变成 0。错误的 lo=mid 会保持 [2,3) 不变，条件仍成立，形成死循环。

查看图表代码

二分为什么终止要看区间长度hi-lo。lo小于hi时中点严格小于hi，每次更新至少排除一个位置，使非负长度严格递减。若把lo改成mid，在只剩一个元素时可能不前进。空数组初始长度为零直接结束。

复杂度与预处理成本

复杂度与预处理成本必须分开：有序随机访问数组的下界查询比较次数为对数，额外空间为常数；本例输入验证扫描为线性，所以完整程序单次工作为线性。反复查询可把验证移到数据导入边界，但须保证随后不被乱序修改。

广度搜索最短路边界

补充反例：S→T 权重 10，S→A 与 A→T 权重均为 1。BFS 按边数会先发现直达 T 的一条边，但总代价 10 大于经过 A 的 2。按层最早发现只证明边数最少，不证明任意权重之和最少。

查看图表代码

广度搜索最短路边界是无权图或各边权重相同。队列按层处理，首次发现时标记避免重复入队。权重不同会破坏首次到达最优的性质；负边更不能套Dijkstra，先检查模型再选择算法。

来源与适用边界

• 英文官方、作者或规范原文：本专题机制依据；按上述固定版本族阅读。
• 中文官方或作者资料：用于术语和讲解交叉核对，冲突以原始规范为准。

算法反例、复杂度取舍与参考

贪心与动态规划反例

dp[1..6] 依次为 1、2、1、1、2、2。计算 dp[6] 时，最后一枚分别为 1、3、4，候选是 dp[5]+1=3、dp[3]+1=2、dp[2]+1=3。枚举最后一步覆盖全部合法方案，取最小才得到 3+3；不能把“优先最大面额”当作通用定理。

查看图表代码

贪心与动态规划反例可用硬币1、3、4组成6：每次拿最大硬币得到4+1+1，最优却是3+3。动态规划定义dp[s]为组成s的最少数量，初值dp[0]=0，不可达为无穷，再枚举最后一枚；不能因少数样例成功就宣称贪心正确。

算法证据复核清单

算法证据复核清单先写输入约束和不变量，再给终止度量与资源界。反例至少包括空输入、重复元素、极端目标和违反前提；测试不能代替证明，但能及时揭示实现与证明不一致。稳定性、字节与字符、溢出分别属于不同契约。

算法原文与旧文索引

算法原文与旧文索引用中文与英文Hello Algo对照区间写法，新课自行推导下界不变量。旧算法单题保留各自实现与锚点；平衡树旋转不是完整AVL，哈夫曼代价函数不是完整编码器，不能将旧单函数等同于完整项目。

来源与适用边界

• 英文官方、作者或规范原文：本专题机制依据；按上述固定版本族阅读。
• 中文官方或作者资料：用于术语和讲解交叉核对，冲突以原始规范为准。
• 相关既有参考：原URL与专业范围保留；历史案例不能自动代表当前实现。