数据结构与算法设计PPT (30).pdf

《数据结构与算法设计PPT (30).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (30).pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 查找7.3 折半查找顺序查找的缺点 顺序查找从列表的开头开始，一直持续到找到该元素或整个表中所有元素都比较完为止 当查找表中元素多时查找效率低折半查找如果查找表中元素有序，折半查找算法比线性搜索更有效。折半查找算法能快速缩小搜索范围，直到查找到或者搜索的范围为空为止折半算法采用分治算法设计折半查找例子a c d f g h j l m o p r s u v x z查找元素j最中间元素查找区间a c d f g h j l m o p r s u v x z查找元素j最中间元素查找区间折半查找例子a c d f g h j l m o p r s u v x z查找元素j最中间元素查找

2、区间折半查找例子a c d f g h j l m o p r s u v x z查找元素j最中间元素查找区间找到啦！折半查找例子012345678-101346810 12lowmidhigh查找6012345678-101346810 12low midhigh012345-101346lowmid high012345678-101346810 12lowmidhigh查找5012345678-101346810 12low midhigh012345-101346lowmid highhighlow折半查找算法类实现折半查找算法算法假定数据元素（从low=0到high=n-1）有序排列

3、template classorderedList:publicdataList /有序表的类定义,继承了数据表public:orderedList(int sz=10):dataList(sz)virtualorderedList()virtual intSearch(const Type&x)const;/查找成功返回值=0 查找失败返回-1;折半查找算法思想采用分治算法的思想：折半算法从序列的中间开始mid=（low+high）/2 将待查找的元素和中间的元素进行比较key Element mid.key：在后半部分中折半查找从 low=mid+1 到high折半查找算法特点 要求查找表

4、中元素按照关键字有序在数组中存放 每次检查“中间”元素-要想快速找到中间元素，要求用顺序存储结构存放 查找算法每次都通过和最中间的元素比较将查找范围缩小到原来的一半 这种分治策略可以快速减少搜索范围template int orderedList:BinarySearch(const Type&x,const int low,const int high)const/折半搜索的递归算法int mid=-1;if(low=high)mid=(low+high)/2;if(Element mid.getKey()x)mid=BinarySearch(x,low,mid-1);return mid;

5、折半查找算法递归算法template int orderedList:BinarySearch(const Type&x)const/折半搜索的迭代算法int high=,low=0,mid;while()mid=(low+high)/2;if(Elementmid.getKey()x);else return mid;return-1;CurrentSize-1low=highlow=mid+1high=mid-1折半查找算法非递归算法012345678910116391471025811左孩子为空Key=21Key=85折半查找算法性能分析05 13192137 5664 7480 889

6、2 最坏情况下查找成功比较次数：log2n +1查找失败情况下比较次数：log2n +1ASLbs=P1C1+P2C2+PnCn=j2j-1=log2(n+1)-1log2(n+1)-1实际情况下查找成功比较次数的计算(1+2*2+3*4+4*4)/11=3=hj 1n1nn1+6391471025811折半查找性能分析折半查找小结 折半查找是一种效率很高的查找算法，时间复杂度是O(logn)对表有要求：顺序存储的有序表 由折半查找的性能分析树可知，查找每个结点所需的比较次数是改结点在树上的层次 折半查找树可知树是一个平衡二叉树，树的高度是 log2n +1 采用折半查找无论查找成功失败查找次数都不会超过树的高度