7.2.1 顺序查找

顺序查找逐项比较，无需有序，适合小表或频繁变动。哨兵可把待查关键字放到边界，循环内省去每轮越界判断，但不能覆盖有效记录。

手工推演

表[4,9,2,7]查2比较3次，查5比较4次。若等概率成功ASL=(1+2+3+4)/4=2.5。

结构与代码

int seq(const int*a,int n,int x){for(int i=0;i<n;i++)if(a[i]==x)return i;return -1;}
```时间O(n)、空间O(1)。

## 正确性

循环不变量：进入第i轮前，0到i-1均不等于x；相等即返回，否则循环后全表不存在。

## 错解反馈

认为无序表能提前因当前值大于x停止；哨兵占用真实数据；失败比较次数写n+1。

## 迁移训练

查找概率不等时怎样降低ASL？答案把高频记录置前，若允许自组织还可命中后前移。