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

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

TableLen=11

查找目标:10131619I293233I374143

low=0►lowmidv=(low+high)/2high=TableLen-1

33>mid,只可能

在右边区域

第1页共22页

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

TableLen=11

查找目标：］

710131619I2932

01234567

lowmidhigh

33<mid,只可能

在左边区域

第2页共22页

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

TableLen=11

查找目标：］

第3页共22页

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

TableLen=11

查找目标：］

012345678910111213

higth

lotw

33==mid

I查找成功

mid

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

TableLen=11

查找目标:

1◄0

-

igh

12<mid,只可能

在左边区域

第4页共22页

第5页共22页

第6页共22页

第7页共22页

折半查找的算法思想

折半查找，又称“二分查找”，仅适用于有序的顺序表。

TableLen=11

查找目标:12

012345678910111213

low>high

查找失败

折半查找的实现

〃折半查找

typedefstruct{//查找表的数据结构（顺序表）intBinary_Search(SSTableL,ElemTypekey){

ElemType*elem;//动态数组基址intlow=0,high=L.TableLen-1,mid;

intTableLen;//表的长度while(low<=high){

}SSTable;mid=(low+high)/2;〃取中间位置

if(L.elem[mid]==key)

mid;//查找成功则返回所在位置

折半查找，又称“二分查找”,return

elseif(L.elem[mid]>key)

仅适用于有序的顺序表。high=mid-l;〃从前半部分继续查找

▲else

low=mid+l;//从后半部分继续查找

顺序表拥有随机访问}

的特性，链表没有return-1;//查找失败，返回一1

}

TableLen=11

查找目标:331013I161929I323337I4143

01234

lowmidhigh

第8页共22页

。•查找•效率•分析。

❷0❾123❾456❺7❾89❷10

。。查找效■率分析。©

❷0❾123❾456❾7❸8❾910

t

mid

第9页共22页

查找效率分析

0000000000

01234678910

查找效率分析

mid

第10页共22页

第11页共22页

查找效率分析

ASL成功=(17+2*2+3*4+4*4)/11=3

ASL失败=(3*4+4*8)/12=11/3

第12页共22页

折半查找判定树的构造

012345678910

lowhigh

折半查找判定树的构造

—0123456❾7❸8❾9。©10

ttt

lowmidhigh

mid=[(low4-high)/2\

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

第13页共22页

折半查找判定树的构造

。mid❾•❾•❷

❷0❾1❽23❾4678910

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

折半查找判定树的构造

0123456789

tI

lowhigh

第14页共22页

。折半查找判定树的构造。

❷0❾12❷34❾56❸7❾89

lowmidhigh

mid=[(low4-high)/2\

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素

折半查找判定树的构造

oeee

012356789

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素

第15页共22页

折半查找判定树的构造

012356789

tttttt

lowmidhighlowmidhigh

mid=[(low+high)/2\

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素

第16页共22页

第17页共22页

折半查找判定树的构造

如果当前low和high之间有奇数个元素，则mid分隔后，左右两部分元素个数相等

如果当前low和high之间有偶数个元素，则mid分隔后，左半部分比右半部分少一个元素

折半查找的判定树中，若mid=[Qow+high)/2」,则对于任何一个结点，必有:

右子树结点数-左子树结点数=0或1

第18页共22页

折半查找判定树的构造

折半查找判定树的构造

判定树结点关键字：左〈中〈右，满足二叉排序树的定义

失败结点：n+1个（等于成功结点的空链域数量）

第19页共22页

折半查找判定树的构造

折半查找的查找效率

树高/?=[log^n+1)]查找成功的ASL<h折半查找的时间复杂度=O(log2n)

注：该树高不包

查找失败的ASL<h

含失败结点

第20页共22页

知识回顾与重要考点

适用范围0只适用于有序的顺序表

在［low,high］之间找目标关键字，每」检查mid=（low+high）/2

算法思想3/根据mid所指元素与目标关键字的大小调整low或high,不断缩小low和high的范围

1若low>high则查找失败

由mid所指元素将原有元素分割到左右子树中

构造O/

■■

折半查找O

判定树d1折半查找的判定树是平衡的二叉排序树（左〈中〈右）

折半查找判定树，只有最下面一层是不满的

〈特性C

若查找表有n个关键字，则失败结点有n+1个

树高〃=170g2（〃+01

\（不包含失败结点）

时间复杂度

拓展思考

折半查找时间复杂度=。（/“©〃）

顺序查找的时间复杂度=。（〃）

辣么，折半查找的速度一定比顺序查找更快?

TableLen=11

查找目标: