专升本（计算机专业课件)数据结构第章课件折半查找key.pdf

《专升本（计算机专业课件)数据结构第章课件折半查找key.pdf》由会员分享，可在线阅读，更多相关《专升本（计算机专业课件)数据结构第章课件折半查找key.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、折半查找的算法思想折半查找，又称“二分查找”，仅适用于有序的顺序表。查找目标:10 13 16 19 I 29 32 33 I 37 41 43TableLen=11low=0 lowmid v=(low+high)/2high=TableLen-133m id,只可能在右边区域第1页 共2 2页折半查找的算法思想折半查找，又称“二分查找”，仅适用于有序的顺序表。查找目标：7 10 13 16 19 I 29 32TableLen=110 1 2 3 4 5 6 7low mid high33mid,只可能在左边区域第2页 共2 2页折半查找的算法思想折半查找，又称“二分查找”，仅适用于有序的

2、顺序表。查找目标：TableLen=11第3页 共2 2页折半查找的算法思想折半查找，又称“二分查找”，仅适用于有序的顺序表。TableLen=110 1 2 3 4 5 6 7 8 9 10 11 12 13查找目标：33=midI查找成功higthlotwmid折半查找的算法思想折半查找，又称“二分查找”，仅适用于有序的顺序表。TableLen=11查找目标:10-igh12high查找失败折半查找的实现/查找表的数据结构（顺序表）/动态数组基址/表的长度折半查找，又称“二分查找”,仅适用于有序的顺序表。顺序表拥有随机访问的特性，链表没有折半查找in t Binary_Search(SST

3、able L,ElemType key)int low=0,high=L.TableLen-1,mid;while(lowkey)high=m id-l;从前半部分继续查找elselow=mid+l;/从后半部分继续查找return-1;/查找失败，返回一1TableLen=11查找目标:3310 13 I 16 19 29 I 32 33 37 I 41 430 12 3 4lowmidhigh第8页 共2 2页。查找效率分析。0123456789 10。查找效率分析。0123456789 10tmid第 9 页 共 2 2 页查找效率分析0 0 0 0 0 0 0 0 0 00 1 2 3

4、 4 6 7 8 9 10查找效率分析mid第 1 0 页 共 2 2 页第1 1页 共2 2页查找效率分析ASL 成功=(17+2*2+3*4+4*4)/11=3ASL 失败=(3*4+4*8)/12=11/3第1 2页 共2 2页折半查找判定树的构造0123456789 10low high折半查找判定树的构造。0 1 23456789 10tttlow mid highmid=(low 4-high)/2如果当前low和high之间有奇数个元素，则m id分隔后，左右两部分元素个数相等第1 3页 共2 2页折半查找判定树的构造。m id 0 1 2 3 4 6 7 8 9 10如果当前l

5、ow和high之间有奇数个元素，则m id分隔后，左右两部分元素个数相等折半查找判定树的构造0123456789tIlow high第 1 4 页 共 2 2 页。折半查找判定树的构造。0123456789lowmidhighmid=(low 4-high)/2如果当前low和high之间有偶数个元素，则m id分隔后，左半部分比右半部分少一个元素折半查找判定树的构造o0 e1 e2 e3 5 6 7 8 9如果当前low和high之间有偶数个元素，则m id分隔后，左半部分比右半部分少一个元素第1 5页 共2 2页折半查找判定树的构造0 1 2 3 5 6 7 8 9t t t t t tl

6、ow mid high low mid highmid=(low+high)/2如果当前low和high之间有奇数个元素，则m id分隔后，左右两部分元素个数相等如果当前low和high之间有偶数个元素，则m id分隔后，左半部分比右半部分少一个元素第1 6页 共2 2页第 1 7 页 共 2 2 页折半查找判定树的构造如果当前low和high之间有奇数个元素，则 mid分隔后，左右两部分元素个数相等如果当前low和high之间有偶数个元素，则 mid分隔后，左半部分比右半部分少一个元素折半查找的判定树中，若mid=Qow+high)/2,则对于任何一个结点，必有:右子树结点数-左子树结点数=

7、0或1第1 8页 共2 2页折半查找判定树的构造折半查找判定树的构造判定树结点关键字：左 中 右，满足二叉排序树的定义失败结点：n+1个（等于成功结点的空链域数量）第1 9页 共2 2页折半查找判定树的构造折半查找的查找效率树高/?=logn+1)查找成功的ASL h 折半查找的时间复杂度=O(log2n)注：该树高不包含失败结点查找失败的ASL h i g h 则查找失败由m i d 所指元素将原有元素分割到左右子树中构造 O/折半查找O判定树 d1折半查找的判定树是平衡的二叉排序树（左 中 右）特性 C折半查找判定树，只有最下面一层是不满的若查找表有n 个关键字，则失败结点有n+1个时间复

8、杂度树高=17 0 g 2（+0 1 （不包含失败结点）拓展思考折半查找时间复杂度=。（/“）顺序查找的时间复杂度=。（）辣么，折半查找的速度一定比顺序查找更快?TableLen=11查找目标:0 1 2 3 4 5 6 7 8 9 10 11 12 13否认三连我不是 我没有 别瞎说啊第2 1页 共2 2页拓展思考如果 mid=(low+high)/2辣么，判定树是什么亚子？涵g。00123456789 10lowmidhighmid=(low 4-力ig)如果当前low和high之间有奇数个元素，则m id分隔后，左右两部分元素个数相等拓展思考midhighmid=(low 4-high)/2如果当前low和high之间有偶数个元素，则m id分隔后，左半部分比右半部分多一个元素如果 mid=(low+high)/2辣么，判定树是什么亚子？第2 2页 共2 2页