查找chazhao

也称检索，或搜索.在大量的信息集合中寻找一个“特定的”信息元素.例如，我们想查某个学生的成绩，给定其姓名或学号，在成绩表中找到该生的位置后，将所记录的各科分数取出来.再如，要查找得100分的学生时，则确定分数中含100分的学生的位置，再将该处学生的姓名或学号取出来，在上述例子中，姓名、学号或特定的分数是查找的关键字，也就是待查找的“特定的”信息元素.学生成绩记录一般是以线性表的顺序存贮结构或链式存贮结构存放在计算机中，称之为表，表有表头和表尾.
查找方法有很多，其主要方法如下：
❶顺序查找 查找过程是，从表头开始，根据给定的值K，依次与表中的关键字进行比较，若关键字与给定值相等，则可查到相应记录，说明查找成功；反之，若直到表尾，仍未找到，则表明无此记录，查找不成功.

❷折半查找（二分法查找） 当表中的关键字已排好序时(这种表称为有序表，比如成绩表是按学号排列的)，可以采用这种方法.查找的过程是，先查看表的中间位置的元素，与给定值K进行比较，若K比表中间位置元素小，说明应在前面找，否则在后面找.
这样，经过一次比较之后，就可以去掉表长的一半.对于剩下的半个表，再重复上述步骤继续查找，查找过程有两种结束情况，其一，位于剩下的半个表表中间位置的元素等于指定值K，则查找成功，取出该处记录；其二，分到最后仍然找不到，则说明所查记录不存在.
例如，含有16个记录的一张有序表，表中数据已按递增排好序，现在要查指定值72在表中的位置.如果要用顺序查找，则要从表头开始逐个比较表中的关键字，经10次比较才能查到72处在表中的位置10.现用二分法查找，过程如下：
第一步(图1)，表头位置LOW=1；表尾位置HIGH=16；中间位置MID=取整〔(LOW+HIGH)/2〕=8，该处的关键字为R (8)=62<72（指定值），说明应去掉表的前一半.剩下的表构成一个新的表.

图1

图2

图3

第二步(图2)，新表的表头位置LOW=MID+1=9；表尾位置HIGH=16，中间位置为MID=取整〔(LOW+HIGH)/2〕=12，该处的关键字为R (12)=76>72（指定值），说明应去掉表的后一半，剩下的表构成一个新表.
第三步(图3)，新表的表头位置LOW=9；表尾位置为HIGH=MID-1=11；中间位置MID=取整〔(LOW+HIGH)/2〕=10，该处的关键字R (10)=72恰等于给定值，查找成功.

图4

从这个例子看出折半查找比顺序查找效率要高.

❸分块查找（索引查找） 这种方法的思路类似于查字典，通过字母的索引表查找到最先出现该字母的那一页，再找到以这字母打头的字词.
例如，图4的左面是索引表.它是按字母次序排列的，可以用顺序查找法或折半查找法来查找索引字母，待找到索引字母后，据索引表所记录的该字母为字头的词的首个词的地址，再去查指定的词.
比如要查找BU，先在索引表中查得字母B的首地址为4，尾地址为7(用D的首地址8减1)然后从地址4到7，很快查到BU为第7个数据.