数据结构-基于C++语言（微课版） 课件 1-1 折半查找

折半查找的算法思想；折半查找的实现；折半查找的性能分析。本节目录：本节内容：折半查找有序表的折半查找

有序表的折半查找

使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。有序表的折半查找

折半查找的基本思想：

[r1………rmid-1]rmid[rmid+1………rn]如果k<rmid如果k>rmid查找左半区查找右半区k（mid=(1+n)/2）有序表的折半查找

例：查找值为14的记录的过程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14非递归算法intBinSearch(intr[],intn,intk)//数组r[1]~r[n]存放查找集合{low=1;high=n;while(low<=high){mid=(low+high)/2;if(k<r[mid]) high=mid-1;elseif(k>r[mid]) low=mid+1;else returnmid;}return0;}有序表的折半查找

有序表的折半查找

递归算法intBinSearch(intr[],intlow,inthigh,intk){if(low>high) return0;else{mid=(low+high)/2;if(k<r[mid])returnBinSearch(r,low,mid-1,k);elseif(k>r[mid])returnBinSearch(r,mid+1,high,k);else returnmid;}}有序表的折半查找

折半查找的查找性能可以使用二叉查找树来分析。树中的每个结点对应有序表中的记录的位置。二叉查找树的构造方法：

⑴当n=0时，二叉查找树为空；

⑵当n＞0时，二叉查找树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的二叉查找树，根结点的右子树是与r[mid+1]~r[n]相对应的二叉查找树。有序表的折半查找

11个结点的二叉查找树的构造－11－22－33－44－510－1111－9－108－97－85－66－7内部结点外部结点3691011784512有序表的折半查找

具有n个结点的二叉查找树的深度为h＝查找成功：在表中查找任一记录的过程，即是二叉查找树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。查找失败：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。从折半查找判定树上容易看出，无论是查找成功还是查找失败，关键码的比较次数都小于等于二叉查找