七、查找
7.1 查找的基本概念
7.1.1 基本概念
查找 —— 在数据集合中寻找满⾜某种条件的数据元素的过程称为查找
查找表（查找结构）—— ⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成
关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的
7.1.2 对查找表的常见操作
① 查找符合条件的数据元素
② 插入、删除某个数据元素
7.2.3 查找算法的评价指标
查找长度——在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度(ASL, Average Search Length)——所有查找过程中进行关键字的比较次数的平均值
ASL 的数量级反应了 查找算法时间复杂度
”
7.2 顺序查找和折半查找
7.2.1 顺序查找
顺序查找：⼜叫“线性查找”，通常⽤于线性表。
算法思想：从头到尾挨个找（或者从尾到头）。
代码实现：
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //动态数组基址
int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
int i;
for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
// 查找成功返回数组下标，否则返回-1
return i=ST.TableLen? -1 : i;
}
“哨兵”方式实现
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //动态数组基址
int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
ST.elem[0]=key;
int i;
for(i=ST.TableLen;ST.elem[i]!=key;--i)
// 查找成功返回数组下标，否则返回0
return i;
}
查找效率：查找成功和查找失败都是O(n)的数量级
一个成功结点的查找长度=自身所在层数
一个失败结点的查找长度=其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生
7.2.2 折半查找
折半查找：⼜称“⼆分查找”，仅适⽤于有序的顺序表。（顺序表拥有随机访问的特性，链表没有）
typedef struct{
ElemType *elem;
int TableLen;
}SSTable;
// 折半查找
int Binary_Search(SSTable L,ElemType key){
int low=0,high=L.TableLen,mid;//先让low和high分别指向队头和队尾的位置
while(low<=high){
mid=(low+high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]>key)
high=mid-1; //从前半部分继续查找
else
low=mid+1; //从后半部分继续查找
}
return -1; //查找失败
}
查找效率分析
折半查找的判定树一定是平衡二叉树
折半查找的判定树中(只有最下面一层是不满的，因此，元素个数为n时树高h =[log2(n+1)]
7.2.3 分块查找
分块查找的特点：块内⽆序、块间有序
分块查找，⼜称索引顺序查找，算法过程如下：
①在索引表中确定待查记录所属的分块（可顺序、可折半）
②在块内顺序查找
// 索引表
typedef struct{
ElemType maxValue;
int low,high;
}Index;
// 顺序表存储实际元素
ElemType List[100];
若索引表中不包含目标关键字，则折半查找索引表最终停在low>high，要在low所指分块中查找
