7.1 查找的基本概念

查找表是同类记录集合，关键字用于识别记录。静态查找只查询，动态查找还会插入删除。平均查找长度 ASL 是各情况比较次数的概率加权和，必须区分成功与失败。

手工推演

记录关键字[8,3,10]，等概率顺序查找成功比较次数为1,2,3，ASL=2；失败需检查3次。若访问概率不同，应按实际概率加权。

结构与代码

选择结构要看是否有序、更新频率、内存层次和操作比例。比较次数不是唯一成本，B树关注磁盘访问，散列还受负载因子影响。

正确性

ASL来自期望定义；每种算法的比较次数应从其状态转移或判定树推出。

错解反馈

把最坏次数当平均；成功ASL和失败ASL混算；只看时间不看更新与空间。

迁移训练

某表3项，访问概率0.6,0.3,0.1，如何排列使顺序查找ASL最小？答案按概率降序，ASL=1.5。