# 1. 查找的基本概念
列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。
关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以惟一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。
查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。对于表的查找，一般有两种情况，一种是静态查找，指在查找过程中只是对数据元素进行查找；另一种是动态查找，指在实施查找的同时，插入找不到的元素，或从查找表中删除已查到的某个元素，即允许表中元素变化。
查找算法中会涉及到三类参量：
①查找对象 K（找什么）；
②查找范围 L（在哪找）；
③K 在 L 中的位置（查找的结果）
其中①、②为输入参量，③为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为 n 的列表，查找成功时的平均查找长度为：ASL=P1C1 + P2C2 +…+ PnCn =∑ pici
其中 Pi 为查找列表中第 i 个数据元素的概率，Ci 为找到列表中第 i 个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。
查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。
其中比较式查找法又可以分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为 HASH（哈希）查找法。
