文档介绍：*
查找
*
查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素
关键字——是数据元素中某个数据项的值，它可以标识一个数据元素
查找方法评价
查找速度
占用存储空间多少
算法本身复杂程度
平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值
基本概念:
*
查找成功—在查找表中找到关键字值等于给定值的记录。
查找失败
对查找表常进行的操作：
查询某个“特定的”数据元素是否在查找表中
检索某个“特定的”数据元素的各种属性
在查找表中插入一个数据元素
从查找表中删除某个元素
静态查找表：对查找表只前两种“查找”操作
动态查找表：对查找表要进行后两种“查找”操作
*
一 顺序查找（线性查找）
查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较
算法描述
i
例
0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找64
64
监视哨
i
i
i
i
比较次数=5
比较次数：
查找第n个元素： 1
查找第n-1个元素：2
……….
查找第1个元素： n
查找第i个元素： n+1-i
查找失败： n+1
*
typedef int KeyType;
typedef float ElemType;
typedef struct
{ KeyType key; //记录的关键字
ElemType info; //记录的其他信息
}JD;
int seqsrch(JD r[], int n, KeyType k) //设置监视哨的算法
{ int i=n;
r[0].key=k;
while(r[i].key!=k)
i--;
return(i);
}
*
int seqsrch(JD r[],int n,KeyType k) //未设置监视哨
{
int i=0;
while (i<n && r[i].key!=k)
i++;
if (i>=n)
return(-1);
else
return(i);
}
*
顺序查找方法的ASL
*
二 折半查找
查找过程：每次将待查记录所在区间缩小一半
适用条件：
顺序存储结构
查找表按关键字排序
算法实现
设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值
初始时，令low=1,high=n,mid=(low+high)/2
让k与mid指向的记录比较
若k==r[mid].key，查找成功
若k<r[mid].key，则high=mid-1
若k>r[mid].key，则low=mid+1
重复上述操作，直至low>high时，查找失败
*
算法描述
low
high
mid
例
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找21
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low
high
mid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low
high
mid
*