在各种数据集合（包括数组、线性表、树等数据结构）中，数据记录在集合中的实际位置是随机的，和数据记录的关键字之间不存在确定的关系。因此在数据集合中查找数据记录时需要进行一系列关键字的比较。查找算法大多数是建立在关键字比较的基础上。

在顺序查找时，比较的结果为” = “与” ≠ “两种可能。在折半查找、二叉排序树查找和树查找时，比较的结果为” < “、” = “与” > “三种可能。查找的效率主要决定于查找过程中所进行的比较次数和时长。在同等关键字模式下，又以比较次数为最主要的因素。

为确定数据记录在被查找集合中的实际位置，需和给定值进行比较的关键字个数（也即比较次数）的期望值称为：查找算法在查找成功时的平均查找长度（Average Search Length）。下面简单讨论一下在含有个数据记录的集合中，几种常见查找算法的平均查找长度。

在等概率的情况下，顺序查找的平均查找长度为：

\[ {ASL}_{ss} = \frac{n+1}{2} \]

对于折半查找（表要求是顺序表），在\(n\)比较大（\(n>50\)）的时候，可有以下近似结果：

\[ {ASL}_{bs} = {\log_2 (n + 1)} -1 \]

在随机情况下（二叉树查找可能退化为顺序查找），对于二叉树，其平均查找长度为：

\[ {ASL}_{b} = 1 + 4{\log n} \]

在平衡二叉树上进行查找，其平均查找长度为：

\[ {ASL}_{bb} = {{\log_\phi} [ {\sqrt 5} (n + 1) ]} – 2 \]

其中，\(\phi = \frac {1+ \sqrt 5}{2}\)。

对于一颗阶的树，从根节点到关键字所在节点的路径上涉及的节点数可以说是平均查找长度的上限：

\[ {ASL}_{B^-} \le {\log_{\frac{m}{2}} \frac{n+1}{2}} + 1 \]

总的来说，这些查找算法的效率都将随着数据记录数\(n\)的增长而下降。仅仅是有的下降得比较快（时间复杂度为\(O(n)\) ，有的下降得比较慢（时间复杂度是 \(O[\log(n)]\) ）而已。

这些查找算法的平均查找长度是在一种比较理想的情况下获得的。在实际应用当中，对数据结构中数据记录的频繁增加和删除将不断地改变着原有的数据结构。这些操作将可能导致某些数据结构退化为链表结构，那么其性能必然将下降。为了避免出现这种情况而采取的调整措施，又不可避免的增加了程序的复杂程度以及操作的额外时间。

拓展阅读

CSDN : 查找算法