本文关于排序算法概述引自《新编数据结构习题与解析》（李春葆等著）第10章及《算法》第3章3.1节。
被查找的对象是由一组记录组成的表或文件，每个记录由若干个数据项组成，并假设每个记录都有一个能唯一标识该记录的关键字。
查找的定义是：给定一个值k，在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。
采用何种查找方法的相关因素如下：
1）使用哪种数据结构来表示“表”，即表中记录是按何种方式组织的；
2）表中关键字的次序，即对无序集合查找还是对有序集合查找。
若在查找的同时对表做修改运算（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。
查找也有内查找和外查找之分。若整个查找过程都在内存中进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找。
由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(Average Search Length)定义为：
其中，n是查找表中记录的个数。pi是查找第i个记录的概率，一般地，均认为每个记录的查找概率相等，即pi=1/n(1<=i<=n)，ci是找到第i个记录所需关键字比较的次数。
平均查找长度分为成功情况下的平均查找长度和不成功情况下的平均查找长度两种，前者指找到表中的某记录平均需要比较关键字的次数，后者指给定的关键字不在表中出现时平均需要比较关键字的次数。
几种查找算法的优缺点列表如下：
|
使用的数据结构 |
实现 |
优点 |
缺点 |
|
链表（顺序查找） |
SequentialSearchST |
适用于小型问题 |
对于大型符号表很慢 |
|
有序数组 （二分查找） |
BinarySearchST |
最优的查找效率和空间需求，能够进行有序性相关的操作 |
插入操作很慢 |
|
二叉查找树 |
BST |
实现简单，能够进行有序性相关的操作 |
没有性能上界的保证，链接需要额外的空间 |
|
平衡二叉查找树 |
RedBlackBST |
最优的查找和插入效率，能够进行有序性相关的操作 |
链接需要额外的空间 |
|
散列表 |
SeparateChainHashST LinearProbingHashST |
能够快速地查找和插入常见类型的数据 |
需要计算每种类型的数据的散列，无法进行有序性相关的操作，链接和空结点需要额外的空间 |