7.2.2 折半查找

折半要求顺序存储且按关键字有序。维护闭区间[low,high]，mid=low+(high-low)/2；x较小令high=mid-1，较大令low=mid+1。

手工推演

数组[2,5,8,12,16,23]查16：mid2值8，low3；mid4值16成功，共2次。查10：8后到区间3..5，比较16，再比较12，最终low>high失败。

结构与代码

int bin(const int*a,int n,int x){int l=0,r=n-1;while(l<=r){int m=l+(r-l)/2;if(a[m]==x)return m;if(a[m]<x)l=m+1;else r=m-1;}return -1;}

正确性

不变量：若x存在，则始终在当前闭区间；每轮排除mid及不可能的一半，区间严格缩短。时间O(log n)。

错解反馈

循环条件写l<r漏单点；更新l=mid导致死循环；链表上折半仍声称高效。

迁移训练

在6项数组查失败最多比较几次？答案3，可由判定树高度或实际边界推演。