-顺序查找方法的ASL 对含有n个记录的表，AL=之Pc i- 设表中每个元素的查找概率相等，- n 则4s=2pe,=121=1+D-n+ n i= n 22
– 顺序查找方法的ASL 2 1 2 1 1 ( 1) 1 1 1 + = + = = = = = = n n n n i n ASL p c n p n i n i i i i 则 设表中每个元素的查找概率相等= = n i i i n ASL p c 1 对含有 个记录的表
·9.1.2折半查找 一查找过程：每次将待查记录所在区间缩小一半 一适用条件：采用顺序存储结构的有序表 一算法实现 ·设表长为n,low、high和mid分别指向待查元素所 在区间的上界、下界和中点，k为给定值 ·初始时，令low=1,high=n,mid=L(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时，查找失败
• 9.1.2 折半查找 – 查找过程：每次将待查记录所在区间缩小一半 – 适用条件：采用顺序存储结构的有序表 – 算法实现 • 设表长为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时，查找失败
一算法描述 找21 1 2 3 4 5 6 7 8 9 10 11 例 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 8 9 1011 5 13 19 2137 5664 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 1011 5 1319 2137 56 64 7580 8892 lowmid high
– 算法描述 low mid high 例 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 mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 lowmid high
找70 2 4 5 7 8 9 例 3 6 10 11 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 1011 5 13 19 21 37 56 64 75 80 88 92 low mid high 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 mid high 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 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 mid high
1 2 3 4 5 6 8 9 10 11 5 1319 21 37 56 64 75 80 88 92 high low 1 2 3 4 5 6 7 8 9 10 11 5 13 19 2137 56 64 75 80 88 92 判定树： 6 9 8
1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low 2 5 8 11 1 4 7 10 3 9 判定树： 6 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92