01234567891011213 中7141821232931353842464952 ②表空测试,非空 mid=5 ③得到中点,比较测试为a情形 low=4 high=4 high=md-1,调整到左半区 ②表空测试,非空; mid=4 ③得到中点,比较测试为b情形 high=4 low=5 loW=mid+1,调整到右半区 ②表空测试,为空;查找失败,返回查找失败信息为0 2021年1月21日 数据结构讲义 26
2021年1月21日 数据结构讲义 26 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ②表空测试，非空； mid=5 ③得到中点，比较测试为a情形 ↑↑ low=4 high=4 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空； mid=4 ③得到中点，比较测试为b情形 ↑ ↑ high=4 low=5 low=mid+1，调整到右半区 ──────────────────────────── ②表空测试，为空；查找失败，返回查找失败信息为0 ────────────────────────────
【算法92】 int Binary Search(S TbL tbl, KEY kx) *在表tbl中査找关键码为kx的数据元素,若找到返回该元素在表中的位置,否则 逐07 int mid, flag=0 low-l; high=length; /*①设置初始区间* while(low<=high /*②表空测试* {/*非空,进行比较测试 mid=(low+high)/2 体*③得到中点* if(kx< tbl elem(mid]key)high=mid-1;/调整到左半区* else if(kxtbl elem mid] key) low=mid+1 调整到右半区* else flag=-mid; break /*查找成功,元素位置设置到fag中* return flag, 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 27 【算法9.2】 int Binary_Search(S_TBL tbl，KEY kx) { /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则， 返回0 */ int mid，flag=0； low=1；high=length； /* ①设置初始区间 */ while(low<=high) /* ②表空测试 */ { /* 非空，进行比较测试 */ mid=(low+high)/2； /* ③得到中点 */ if (kx<tbl.elem[mid].key) high=mid-1； /* 调整到左半区 */ else if(kx>tbl.elem[mid].key) low=mid+1； /* 调整到右半区 */ else { flag=mid；break；} /* 查找成功，元素位置设置到flag中 */ } return flag; }
【性能分析】 从折半查找过程看,以表的中点为比较对象,并以中点将 分割为两个子表,对定位到的子表继续这种操作。所以, 对表中每个数据元素的查找过程,可用二叉树来描述,称这 个描述查找过程的二叉树为判定树。 42 2③35 图92例91描述折半查找过程的判定树 2021年1月21日 数据结构讲义 28
2021年1月21日 数据结构讲义 28 【性能分析】 从折半查找过程看，以表的中点为比较对象，并以中点将 表分割为两个子表，对定位到的子表继续这种操作。所以， 对表中每个数据元素的查找过程，可用二叉树来描述，称这 个描述查找过程的二叉树为判定树。 49 29 38 18 7 42 52 31 23 46 35 14 21 图9.2 例9.１描述折半查找过程的判定树
可以看到,查找表中任一元素的过程,即是判定树 中从根到该元素结点路径上各结点关键码的比较次数, 也即该元素结点在树中的层次数。对于n个结点的判定树, 树高为k,则有2k1-1<m≤2k-1,即k-1<log2nt+1)≤k,所以 k=「og2(n+1) 因此,折半查找在查找成功时,所进行的关键码比较次 数至多为 og2(n+1) 接下来讨论折半查找的平均查找长度。为便于讨论, 以树高为k的满二叉树(n=2-1)为例。假设表中每个元素的 查找是等概率的,则树的第层有2-1个结点,因此,折半 查找的平均查找长度为: 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 29 可以看到，查找表中任一元素的过程，即是判定树 中从根到该元素结点路径上各结点关键码的比较次数， 也即该元素结点在树中的层次数。对于n个结点的判定树， 树高为k，则有2 k-1 -1<n≤2 k -1，即k-1<log2 (n+1)≤k，所以 k= 。 因此，折半查找在查找成功时，所进行的关键码比较次 数至多为 。 接下来讨论折半查找的平均查找长度。为便于讨论， 以树高为k的满二叉树(n=2 k -1)为例。假设表中每个元素的 查找是等概率的，则树的第i层有2 i-1个结点，因此，折半 查找的平均查找长度为： log 2 (n +1)
ASL 2 =(1m)1×20+2×2++k×2k =(n+1)m)log2(n+1)-1≈log2(m+1-1 所以,折半查找的时间效率为O(ogn)。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 30 ASL= Pi·Ci n ∑i=1 =(1/n)[1×2 0+2×2 1+…＋k×2 k-1 ] =((n+1)/n) log2 (n+1)-1≈log2 (n+1)-1 所以，折半查找的时间效率为O(log2 n)