查找总括
查找的常用方法
- 顺序查找
- 折半查找
- 分块查找
- B树
- B+树
- 散列表
查找的相关概念
- 查找的概念
- 在数据集合中寻找满足某种条件的数据元素的工程。
- 查找表
- 用于查找的数据集合，由同一种数据类型（或记录）组成，可以是一个数组或链表等数据类型
- 操作
| 查询某个特定的数据元素是否在查找表中 | 检索满足条件的某个特定的数据元素的各种属性 |
|---|---|
| 在查找表中插入一个数据元素 | 从查找表中删除一个数据元素 |
- 关键字
- 关键字中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
- 平均查找长度
- 查找时，关键字比较次数的平均值。
- 排序树
-
描述查找过程的二叉排序树
顺序查找判定树.JPG
折半查找判定树.JPG
查找方式详解
1.顺序查找
- 顺序查找又称线性查找，主要用于在线性表中进行查找。
- 代码
typedef struct{
ElemType *elem；
int TableLen;
}
int Search_Seq(SStable ST,ElemType key){
ST.elem[0]=key;//哨兵
/*省去查找是否成功的判断过程*/
for(int i=ST.TableLen;ST.elem[i]!=key;i--);// 从后向前查找，因为哨兵的值等于关键字，如果集合中没有相匹配的关键字，循环就会在哨兵处终止，i=0；
return i;
}
-
无序线性表使用顺序查早平均查找长度
顺序查找平均查找长度.JPG -
有序线性表使用顺序查早平均查找长度
根据判定树进行计算
有序序列顺序查找平均查找长度.JPG
Cj=失败结点所在判定树层数（lj）-1；
注意
- 对关键字无序线性表进行顺序查找，查找失败时要遍历整个线性表。
- 对关键字有序线性表进行顺序查找，查找失败时不一定要遍历整个线性表。
2.折半查找
- 折半查找又称二分查找，仅适用于有序的顺序表。
- 算法思想
1.首先将给定值key与表中中间位置元素的关键字进行比较。
2.若相等，则返回该元素的位置
3.若不等，则在前半部分或者后半部分进行查找。
4.重复该过程，直到找到查找的元素为止；或查找失败。 - 代码
int Binary_Search(SeqList L,ELemType key){
int low=0,high=L.Length,mid;
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;
}
-
查找失败时平均查找长度
折半查找判定树.JPG
平均查找长度.JPG
注意
- 折半查找的时间复杂度为O(log2N)
折半查找与顺序查找的应用范围
- 顺序查找适用于顺序存储和链式存储，序列有序无序皆可；折半查找只适用于顺序存储，且要求序列一定有序。
3.分块查找
- 分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点。
- 如何分块
- 将查找表分为若干子块。块内的元素可以无序，但块间是有序的，即 对于所有块有 第i块的最大关键字小于第i+1块的所有记录的关键字。
- 建立索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排序。
块内无序，块间有序
- 如何分块
- 在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表。
- 在块内进行顺序查找。
- 平均查找时间
- 分块查找的平均查找长度为索引值(LI)和块内查找(LS)之和
- 若块内和和块间村采用顺序查找。且长度为n的查找表均分为b块，每块有s个记录。
ASL=LI+LS=(b+1)/2+(s+1)/2=(S^2+2S+n)/2s;当s=√n时平均查找时间最小为√n + 1
3.若块内采用顺序查找，块间采用折半查找
ASL=LI+LS=[log2(b+1)]+(S+1)/2
