目录
前言
关于查找
一、顺序查找法
二、折半查找法
三、分块查找法
四、分析与总结
前言
在非数值运算问题中，数据存储量一般很大，为了能在大量信息中找到某些值，就需要用到查找技术。而为了提高查找效率，就需要对一些数据进行排序。查找和排序是两大重要技术，其数据处理量几乎占到数据总处理量的80%以上，所以查找与排序的有效性直接就影响到基本算法的有效性。本篇文章主要来讨论查找技术中的静态查找，主要包括顺序查找法、折半查找法以及分块查找法。
关于查找
查找表：是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，没有严格的前驱和后继的关系，因此查找表是一种应用灵活的结构。
关键字： 用来标识一个数据元素(或记录)的某个数据项的值。
主关键字：可唯一地标识一个记录的关键字次关键字：用以识别若干记录的关键字
查找成功与否
若查找表中存在这样一条记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置。否则称“查找不成功”。查找结果给出“空记录”或“空指针”
查找目的
查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；删除查找表中的某个数据元素。
查找的分类
静态查找表： 仅作“查询”(检索)操作的查找表，即查找前后，表没有变化。动态查找表：作“插入”和“删除”操作的查找表。有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素，此类表为动态查找表。
查找算法的评估方法
关键字的平均比较次数——平均查找长度(ASL,Average Search Length)
n: 表示记录的总个数
Pi:表示查找第i个元素的概率，一般认为是等概率事件，即：Pi=n/1
Ci:表示找到第i个记录所需要的比较次数
一、顺序查找法
1.特点：用所给出的关键字与线性表中的各个元素进行比较，直到成功或者失败。其存储结构一般为顺序存储结构，也可以是链式存储结构。
2.代码：
//顺序查找法#include<stdio.h>#define LAST_SIZE 20typedef struct{int r[LAST_SIZE];//r[0]为工作单元， 作为"监视哨"的存储位置 int length;}RecordList;//使用"监视哨"法进行顺序查找 int search1(RecordList h, int k){int i;h.r[0]=k;//将关键字赋给r[0]作为"监视哨"i=h.length;//i从表尾位置开始向前移动逐个比较，当全部比较完后还没有找到关键字//则会移动到第0个位置，即"监视哨"位置，而结束循环返回0 while(h.r[i]!=k) i--;return (i); }//测试 int main(){RecordList h;int i,key,j;printf("请输入表的长度：");scanf("%d",&h.length);printf("请输入%d个值将顺序表初始化：\n",h.length);for(i=1;i<=h.length;i++){scanf("%d",&h.r[i]);}printf("请输入你要查找的值：");scanf("%d",&key);j=search1(h,key);if(j!=0)printf("查找成功！\n该元素的位置为：%d\n",j);elseprintf("查找失败！\n");return 0;}
3.运行结果 ：
4.不用监视哨法函数代码
//不使用"监视哨"法进行顺序查找int search2(RecordList h,int k){int i=h.length;while(i>=1&&h.r[i]!=k) i--;if(i>=1)return (i);elsereturn 0;}
5.小结
在数组r的第0个位置作为“监视哨”存放待查找值，当从后往前至第1个位置还没找到待查找的元素，则将遇到监视哨而终止循环，即查询失败！监视哨的主要作用是防止越界。
而不用监视哨法中多了一条循环条件判断语句：i>=1,也是用来检查是否越界的。利用监视哨可以省去这一语句，从而提高查找的效率，这就是使用监视哨法的好处。
二、折半查找法
折半查找法在我之前写过的一个博客中
传送门：数据结构之折半查找法——C语言实现
三、分块查找法
1.算法思想
首先将列表分成若干个子块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每一个块中元素可以任意排列，即块内无序，块间有序。
然后构造一个索引表，其中每个索引项对应一个块，并记录每块的起始位置，以及块中的最大元素，即最大关键字，按最大关键字将块与块排序，达到块间有序。
图解：
从上图中可以看出，索引表将主表分为4块，每块包含5个元素。
要想查找主表中的某个元素，需要分为两步查找：第1步需要确定要查找元素所在的块，第2步在该单元查找指定的元素。例如，要查找元素31，首先需要将31与索引表中的元素进行比较，因为26<31<46，所以需要在第2个块中查找，该快的起始下标是5，因此从主表中的下标为5的位置开始查找31，直到找到该元素为止。如果在该块中没有找到31，则说明主表中不存在该元素，则查找失败。
