文档介绍：查找(检索)
1. 定义
确定给定值 k 在含有 n 个记录的文件中的位置的过程称为查找。
2. 查找算法的度量
用平均查找长度 ASL 来度量:
查找的基本概念
其中,n:记录个数,Pi:查找第i个记录的查找概率, Ci:找到第i个记录的比较次数。
若Pi=1/n(等概),则
1
第二章常用数据结构及其运算
1. 方法
从第一个记录开始,逐个比较记录值:
找到与k相等的记录,查找成功;
否则,查找失败。
查找
线性查找(顺序查找)
例: (5,13,17,42,55,70,94)
查找k=55,比较5次,查找成功,
查找12,则失败。
2
第二章常用数据结构及其运算
线性查找
2. 算法描述
SeqSearch(r[],n,k) { r[n].key=k; i=0; while (r[i].key<>k) i++; return(i); } 说明:若返回n表明查找不成功。
3. 性能分析
查找
等概
3
第二章常用数据结构及其运算
--又称二分查找、折半查找,属于有序表的查找。
1. 基本思想
先找到“中间记录”,比较其关键字,如果关键字与给定值K相等,则查找成功;否则中间结点将线性表分成两个子表,若关键字小于K,则在前半部分子表中查找;反之在后半部分子表中查找。这样把搜索区间缩小了一半。重复以上过程,直到找到与k相等的关键值。(递增排列情况)
查找
对分查找
4
第二章常用数据结构及其运算
2. 方法
1)初始化:设顺序表r[1:n],low-搜索范围下界,high-搜索范围上界,mid-中间位置(low+high)/2
查找
对分查找
m
h
l
l
h=m-1
h
l=m+1
2)r[mid].key=k: 查找成功;
r[mid].key>k: 令high=mid-1 继续查找;
r[mid].key<k: 令low=mid+1 继续查找。
3)直到low>high,查找失败
5
第二章常用数据结构及其运算
5 13 17 42 46 55 70 94
low mid hig
k=55
5 13 17 42 46 55 70 94
low mid hig
查找成功
5 13 17 42 46 55 70 94
low mid hig
5 13 17 42 46 55 70 94
low mid hig
k=12
5 13 17 42 46 55 70 94
low mid hig
5 13 17 42 46 55 70 94
hig low
查找失败
例:
6
第二章常用数据结构及其运算
3. 算法描述
BinSearch(r[],n,k) { low<-0; hig<-n-1; while (low<hig){ mid=(low+hig)/2; if (k==r[mid].key) return(1); if (k<r[mid].key) hig=mid-1; if (k>r[mid].key) low=mid+1; } return(0); }
查找
对分查找
7
第二章常用数据结构及其运算
对分查找
4. 算法分析
对分查找的判定树:把比较次数相同的记录放在同一层次,各层次之间用分支相连,可得到一棵二叉树,称为判定树。对分查找恰好是一条从判定树根到被查结点的一条路径,而比较次数恰好是树的深度。
42
94
55
70
46
13
17
5
序列:5,13,17,42,46,55,70,94的判定树
查找
8
第二章常用数据结构及其运算
对分查找
4. 算法分析
等概率下的平均查找长度:
查找
等概
n<30时,对分查找的优势不明显
9
第二章常用数据结构及其运算
将数据分成若干块
块与块间数据有序
块内数据无序
1. 算法思想
①将各块中的最大关键字构成一个递增有序的索引表
②先查找索引表(采用对分或顺序查找),以确定所在块
③在所在块中进行顺序查找
查找
分块查找(索引顺序查找)
10
第二章常用数据结构及其运算