顺序(线性)表的查找 第九章查找 一说明: (1)顺序查找算法简单,且对表的结构无任何要求(无论按 向量还是链表结构,无论记录间是否按关键字有序排列),故此 算法适应面广。但当n>1时,查找效率随n越大而越低。 (2)当表中各个记录的查找概率互不相等时,为了提高查找 效率,宜将诸记录先按查找概率由小到大进行排列(式(9-2)在 PsP2≤…≤P1P时达到极小值) (3)在很多实际应用的情况下,各记录的查找概率无法事先 确定,则可以采用“自组织”形式的顺序查找表。 第1页
第九章 查找 第11页 (2) 当表中各个记录的查找概率互不相等时，为了提高查找 效率，宜将诸记录先按查找概率由小到大进行排列（式(9-2)在 P1≤P2≤···≤Pn-1≤Pn时达到极小值）； 说明： (1) 顺序查找算法简单，且对表的结构无任何要求（无论按 向量还是链表结构，无论记录间是否按关键字有序排列），故此 算法适应面广。但当n>>1时，查找效率随n越大而越低。 顺序（线性）表的查找 (3) 在很多实际应用的情况下，各记录的查找概率无法事先 确定，则可以采用“自组织”形式的顺序查找表
有序表的查找一一折半查找 第九章查找 折半查找又称二分查找( Binary search),它是一种效 率高的查找方法 折半查找的前提是静态查找表是有序表,即表中记录按 关键字有序排列,且需使用向量作为表的存储结构。不妨设 有序表是递增有序的。 猜数游戏的方法 折半查找的算法思想:° 先确定待査记录所在的范围(区间),然后以处于区间 中间位置记录的关键字和给定值K相比较,(1)若相等,则 查找成功;(2)若不等,则缩小范围,继续按此法查找, 直至新的区间位置记录的关键字等于给定值K,或者查找区一 间的大小等于零(表明查找不成功)时为止 一第12页
第九章 查找 第12页 有序表的查找——折半查找 折半查找又称二分查找（Binary Search），它是一种效 率高的查找方法。 折半查找的前提是静态查找表是有序表，即表中记录按 关键字有序排列，且需使用向量作为表的存储结构。不妨设 有序表是递增有序的。 折半查找的算法思想： 先确定待查记录所在的范围（区间），然后以处于区间 中间位置记录的关键字和给定值K相比较，（1）若相等，则 查找成功；（2）若不等，则缩小范围，继续按此法查找， 直至新的区间位置记录的关键字等于给定值K，或者查找区 间的大小等于零（表明查找不成功）时为止。 猜数游戏的方法
有序表的查找—一折半查找 第九章查找 有序表的折半算法描述 int Search Bin( sSTable st KeyType key //在有序表st中折半查找关健字等于给定值key的记录 int mid 1ow=1;hig=st. Length;//置区间初值 whi1e(1 ow s hig)//判别查找区间大小 mid =( low+ hig ) switch( case K> st elem [mid]. key: low= mid+1; case K = st elem [mid]. key: return mid case K st elem[mid]. key: hig= mid-1 return(0);//查找不成功 算法9.2 第13页
第九章 查找 第13页 有序表的折半算法描述 int Search_Bin( SSTable st, KeyType key ) { //在有序表st中折半查找关健字等于给定值key的记录 int mid; low = 1; hig = st.Length; //置区间初值 while( low ≤ hig ) //判别查找区间大小 { mid = ( low + hig ) / 2; switch{ case K ＞ st.elem[mid].key: low = mid+1; case K == st.elem[mid].key: return mid; case K ＜ st.elem[mid].key: hig = mid-1; } } return( 0 ); //查找不成功 } // 算法 9.2 有序表的查找——折半查找
有序表的查找—一折半查找 第九章查找 算法性能分析 折半查找过程中可用二叉树来描述(判定树)。树根为表的 中间记录。根的左子树关键字均小于根的关键字,根的右子树关 键字均大于根的关键字 示例1:以下11个数据元素为例,可画出二叉树 0513192137566475808892 56 这棵二叉树并非完全二叉 (6 树,但其叶结点所在层次之差 19 至多为1。因此,该二叉树深 (3 80(9 度与一根完全二叉树相同, 05 2 为Llog2n」+1。这里n是二叉 64 88 0树结点的个数,亦即有序表中 数据元素的个数 1337 2 5 75 8) 9211 第14页
第九章 查找 第14页 算法性能分析 6 3 9 1 4 7 I0 2 5 8 11 56 80 64 88 13 37 75 92 05 19 21 这棵二叉树并非完全二叉 树，但其叶结点所在层次之差 至多为1。因此，该二叉树深 度与一根完全二叉树相同， 为 。这里n是二叉 树结点的个数，亦即有序表中 数据元素的个数。 折半查找过程中可用二叉树来描述（判定树）。树根为表的 中间记录。根的左子树关键字均小于根的关键字，根的右子树关 键字均大于根的关键字。 05 13 19 21 37 56 64 75 80 88 92 示例1：以下11个数据元素为例，可画出二叉树 有序表的查找——折半查找
有序表的查找—一折半查找 第九章查找 结论:折半查找法在査找成功时进行比较的关键字个数最多 不超过树的深度,即Log2n+1 问题:查找不成功的情况如何? 示例2对于如示例1所给数据,描述折半查找过程加上外部 结点的判定树和查找关健字为85的结点,示意如下 56 结论:折半查找在 查找不成功时和给 19 80(9 定值进行比较的关 健字个数最多不超 5624 64 88 0 上1132)3436 5 92 6-7 8)9-10 12]23]456]-=741910 图93加上外部结点的判定树和查找85的过程 第15页
第九章 查找 第15页 结论：折半查找法在查找成功时进行比较的关键字个数最多 不超过树的深度，即 问题：查找不成功的情况如何？ 示例2 对于如示例1所给数据，描述折半查找过程加上外部 结点的判定树和查找关健字为85的结点，示意如下 6 3 9 7 I0 56 80 64 88 05 19 21 1 4 6-7 8 9-10 I1 13 3-4 5 37 -1 2 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11- 75 92 图9.3 加上外部结点的判定树和查找85的过程 结论：折半查找在 查找不成功时和给 定值进行比较的关 健字个数最多不超 过 有序表的查找——折半查找