查找概述

**查找（Searching）**是在数据集合中确定关键字等于给定值的数据元素（或判定不存在）的过程。

本文解决什么问题

• 查找要评价什么指标
• 顺序 / 二分 / 哈希如何选型
• 本章各篇分工

本部分学什么

文章	内容
顺序查找	逐个比较，适用任意表
二分查找	有序表上的减治查找
哈希表	由关键字直接计算位置
哈希冲突处理	开放定址、链地址等

衡量指标

指标	含义
平均查找长度 ASL	成功（或失败）查找的平均比较次数
时间复杂度	成功 / 失败情形
静态 / 动态	是否频繁插入删除
是否有序	能否用二分等有序方法

选型直觉

条件	更合适
无序、表很小	顺序查找
有序且可随机访问、少改动	二分查找
动态、按键高频查	哈希表
要有序遍历 / 范围查询	平衡树（std::map）等

小结

先明确数据是否有序、是否需要高效更新，再在顺序、二分、哈希之间选型。

下一篇：顺序查找。