算法与数据结构-查找.ppt

内查找 整个查找过程都在内存中进行。
外查找 在查找过程中需要访问外存。
平均查找长度ASL——查找方法时效的度量
为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。
查找成功时的ASL计算方法：
n：记录的个数
pi：查找第i个记录的概率，
( 不特别声明时认为等概率 pi =1/n )
ci：找到第i个记录所需的比较次数
约定：无特殊说明，一般默认关键字的类型为整型
BUPT
BUPT SCST
第一页，共65页。
顺序表的查找
0 1 n-1 n
r[0..n] a0 a1 an-1 r[n].key=K
[算法描述]
int seqsearch (int *a, const int n, const int K )
{
int i = 0; a[n] = K;
while (a[i] != K) i++;
return i;
}
BUPT
BUPT SCST
第二页，共65页。
[程序设计技巧] 设置监视哨，提高算法效率。
[性能分析]
空间：一个辅助空间。
时间：
1) 查找成功时的平均查找长度
设表中各记录查找概率相等
ASLs(n)=(1+2+ ... +n)/n =(n+1)/2
2)查找不成功时的平均查找长度 ASLf =n+1
[算法特点]
算法简单，对表结构无任何要求
n很大=>查找效率较低
改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。
BUPT
BUPT SCST
第三页，共65页。
二分查找
满足 r[i].key  r[i+1].key, 0 i <n-1
仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。
[折半(二分)查找法]
1 2 3 4 5 6 7 8 9 10 11
05 13 19 21 37 56 64 75 80 88 92
low mid high
=(low+high)/2
K=21 l h m K=85 l h m
1 11 6 1 11 6
1 5 3 7 11 9
4 5 4 10 11 10
10 9
BUPT
BUPT SCST
第四页，共65页。
[算法描述]
int binsearch ( int K, int v[ ], int n )
{
int low, high, mid;
low = 1;
high = n;
while ( low <= high )
{
mid = ( low + high ) / 2;
if ( K < v[mid] )
high = mid - 1;
else if ( K > v[mid] )
low = mid + 1;
else /* 找到了匹配的值*/
return mid;
}
return -1; /* 没有查到*/
}
BUPT
BUPT SCST
第五页，共65页。
[性能分析]

h=l