教育部—微软精品课程建设项目 在不等概率查找的情况下,ASL在 Pn=Pn1=…=P2≥P1 时取极小值 若查找概率无法事先测定,则查找 过程采取的改进办法是,在每次查找之 后,将刚刚查找到的记录直接移至表尾 的位置上。 南京航空航天大学数握结构裸题组版权所有
若查找概率无法事先测定，则查找 过程采取的改进办法是，在每次查找之 后，将刚刚查找到的记录直接移至表尾 的位置上。 在不等概率查找的情况下，ASLss在 Pn≥Pn-1≥···≥P2≥P1 时取极小值
教育部—微软精品课程建设项目 二、有序查找表 上述顺序查找表的查找算法简单, 但平均查找长度较大,特别不适用 于表长较大的查找表 若以有序表表示静态查找表,则 查找过程可以基于“折半”进行。 京航空航天大学数据结构题组版权所有
上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用 于表长较大的查找表。 二、有序查找表 若以有序表表示静态查找表，则 查找过程可以基于“折半”进行
教育部—微软精品课程建设项目 例如:key=64的查找过程如下 STlength STele 0513192137566475808892 01234567891011 low high low指示查找区间的下界 high指示查找区间的上界 mid=(low+high)/2 京航空航天大学数据结构题组版权所有
05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elem ST.length 例如: key=64 的查找过程如下： low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2
教育部—微软精品课程建设项目 int Search Bin( SSTable ST, Key Type key)& low=1;high= STlength;∥置区间初值 while (low <=high)& mid=(low high)/2 if (EQ (key, ST elem[mid] key)) return mid;∥找到待查元素 else if Lt (key, STelem[mid]. key)) high=mid-1;∥继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return o ∥顺序表中不存在待查元 }∥ Search bin 京航空航天大学数据结构题组版权所有
int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin
教育部—微软精品课程建设项目 分析折半查找的平均查找长度 先看一个具体的情况,假设:n=11 i1234567891011 Ci34234134234 判定树 9 7 10 南京航空航天大学数握结构裸题组版权所有
先看一个具体的情况，假设：n=11 分析折半查找的平均查找长度 6 3 9 1 4 2 5 7 8 10 11 判定树 i 1 2 3 4 5 6 7 8 9 10 11 Ci 3 4 2 3 4 1 3 4 2 3 4