4.5.1 顺序查找、折半查找（二分查找）

基本概念

查找表：由同类元素构成的集合。
查找表按照是否可以修改数据表，可分为静态查找表、动态查找表。
静态查找表：不能修改数据表，可进行查询、检索操作。查询是指判断元素是否存在于数据表中。检索是指找到对应元素，获取其属性等相关信息。
动态查找表：可以修改数据表，除了查询、检索外，还能够向数据表插入、删除数据。
关键码：用于标识某个数据项的值。主关键码可以唯一标识数据元素，次关键码能标识多个数据元素。
查找算法：主要操作是将给定值与关键码进行比较，比较成功，则意味着查找成功，否则查找失败。
平均查找长度ASL：可用于衡量查找算法，其计算的是找到关键码时，与给的值进行比较的次数的期望。

顺序查找

顺序查找就是从数据表的第1条记录开始，逐条与给定值进行比较，直到查找成功。如果整个数据表比较完毕，仍未找到，则查找失败。
顺序查找适用于顺序存储的线性表、链表存储的线性表。
顺序查找方法简单，有无关键码都可以应用。但是数据表中元素较多时，其平均查找长度大。

折半查找（二分查找）

折半查找是使用给定值与中间位置的值进行比较，如果相等则查找成功。否则，缩小比较范围，重复上述步骤，直到查找成功/查找失败。
折半查找适用于数据有序，且数据表不需要变动的情况。
折半查找的效率高，但是需要数据提前做好排序。

索引顺序查找

索引顺序查找，先将数据分成若干块，块之间是有序排列的，块内数据是无序的。其查找效率介于顺序查找和折半查找之间。