LV005-查找简介

一、查找

1. 查找表

设记录表 $L=(R_1,R_2,\dots \dots ,R_n)$，其中 $R_i(l\le i\le n)$ 为记录，对给定的某个值 k ，在表 L 中确定 key = k 的记录的过程，称为查找。若表 L 中存在一个记录 $R_i$ 的 key = k ，记为 $R_i.key=k$，则查找成功，返回该记录在表 L 中的序号 i (或 $R_i $ 的地址)，否则(查找失败)返回 0 (或空地址 NULL )。表 L 就称为 查找表，它是是由同一类型的数据元素构成的 集合。

在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为 静态查找表，静态查找表既可以使用顺序表表示，也可以使用链表结构表示。反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为 动态查找表。

2. 查找方法

查找的方法有这几种：顺序查找，二分查找（折半查找），分块查找和 hash 表查找等。

3. 平均查找长度

对查找算法，主要分析其 T(n) （时间复杂度）。查找过程是 key 的比较过程，时间主要耗费在各记录的 key 与给定 k 值的比较上。比较次数越多，算法效率越差（即 T(n) 量级越高），故用比较次数刻画算法的 T(n) 。

平均查找长度 ASL （ Average Search Length ）：对给定 k ，有 n 个元素的查找表 L 中记录比较次数的期望值(或平均值)，即

$$ASL=\sum _{i=1}^n{P}_i{C}_i$$

$P_i$ 为查找 $R_i$ 的概率。等概率情况下 $P_i=1/n$；$C_i$ 为查找 $R_i$ 时 $key$ 进行的比较次数(或查找次数)。