对分查找算法复习

课题：《对分查找算法》复习对分查找算法一、生活中的对分查找淘宝网上热卖的终极飞翼擎天柱（猜价格游戏）游戏规则如下：（1）在给出这个玩具的价格是在100到200之间的整数。

（2）竞猜价格时，先猜100-200之间的中间价格，如果太小了，就猜150－200之间的中间价格，依此类推…

直到猜对为止。我来试试（我愿意一试）150＂太小＂175＂太大＂163＂太小＂169＂太小＂172＂太大＂170＂恭喜您猜对了＂二、“对分思想，验证奇迹”1.对分查找的基本思想：（1）前提：被查找的数据序列必须是有序的。（2）基本思想：在有序的数据序列中（一般放在数组中），首先把查找的数据与数组中间位置的元素进行比较，若相等，则查找成功并退出查找；否则，根据数组元素的有序性，确定数据应在数组的前半部分还是在后半部分查找；在确定了新的查找范围后，重复进行以上比较，直到找到或未找到为止。验证奇迹：

对分查找实际数据演示动画3.算法的基本框架：说明：要查找的数为key，待查找的数存在数组d中。i为查找范围的起点，j为查找范围的终点，m为范围[i,j]的中间位置，find为查找成功与否的标记，find为true代表查找成功；find为false代表查找失败。

i=1j=16find=false‘查找的结果，若为true表示找到，若为false表示未找到

dowhile(i<=j)andnotfind(还未查找完且未找到

)

计算中点的位置m

比较key与d(m)，若key=d(m)，则find=true

若key>d(m)，则重新调整查找范围i=m+1[i,j]

若key<d(m)，则重新调整查找范围j=m-1[i,j]Loop

若find为真，表示查找成功，并输出找到的位置m；若find为假，表示查找失败。4.对分查找算法的流程图实现：请将①②③④补充完整：①

.②.③.④.开始①?i=1,j=16,find=flase②Key=d(m)?Key>d(m)?③④未找到，输出信息找到，输出m结束NYYNYNfind=true?find=trueYN三、“琢玉成形，化玉为器”—

转化为程序代码通过上述16个数据中查找key过程，程序代码如下：i=1:j=16:find=falseDowhile(i<=j)andnotfind‘如果还未找完并且未找到

m=(i+j)\2‘计算中间点位置

ifkey=d(m)then

find=true‘表示查找到的情况elseifkey>d(m)then‘表示待查数据比中间位置上的数大时

i=m+1‘重新调整查找范围的起始位置i=m+1else‘表示待查数据比中间位置上的数小时

j=m-1‘重新调整查找范围的终点位置j=m-1endifLoopIffindthen‘判断查找的结果，若为true表示找到，若为false表示未找到

label1.caption="找到！该数在数组中的位置为："+Str(m)elselabel1.caption="未找到！该数在数组中不存在！“endif通过上述16个数据中查找key的过程，推广至n个数据中查找：

i=1:j=n:find=falseDowhile(i<=j)andnotfindm=(i+j)\2(m=int((i+j)/2)或m=fix((i+j)/2))ifkey=d(m)thenfind=trueelseifkey>d(m)theni=m+1elsej=m-1endifLoop

Iffindthenlabel1.caption="找到！该数在数组中的位置为："+Str(m)elselabel1.caption="未找到！该数在数组中不存在！“

endif打开[上机实践]文件夹中的“对分查找.vpb”文件，将窗体中“对分查找”按钮事件过程(Command3_Click()

)中的代码补充完整。（注：带红色？处）并调试程序使之运行成功。四、“体验之旅，感受程序魅力”1.对分查找算法中被查找数据是降序的情况程序该如何修改？i=1:j=n:find=falseDowhilei<=jandnotfindm=(i+j)\2(m=int((i+j)/2)或m=fix((i+j)/2))ifkey=d(m)thenfind=trueelseifkey>d(m)then

①.else

②.endifLoop

Iffindthenlabel1.caption="找到！该数在数组中的位置为："+Str(m)elselabel1.caption="未找到！该数在数组中不存在！“

endif五、“思想升华，化茧成蝶”2.对分算法几个注意问题：（1）对分查找的前提：被查找数据必须是有序的。（2）新的查找范围的确定：i=m+1或j=m-1

（3）查找结束的判断条件：找到数据(find=true)或i>j3.对分查找算法的最多查找次数：Log2n+14.对分查找算法的实际意义：对分查找的高效性。（1）一个包含一百万个人名的电话簿中找一个名字，对分查找可以让你不超过20次就能找到指定的名字。（2）将全国13亿人按身份证号排列后，你可在31次比较后找到这个人的信息。若用顺序查找还有这个效率吗？假设每次对分最坏情况，直到最后一次才找到

就会有

2^k

=

n

/

2

得到

k

=

long2n

+

1；二分法每次都会把范围缩小一半，因为最后剩一个元素时，也要执行查找过程，所以+1。六、“夯实基础，查漏补缺

”某8位男生的肺活量数据放在数组元素a(1)到a(8)中，其数据依次为：3205、3408、3471、3498、3621、3829、4233、

4540，使用对分查找，设定查找键key，若第一个被访问到的数据是3498，小于key值，则第二个被访问到的数据是（）

A、3408B、3829C、4233D、45402.某数组有7个元素，依次为200、202、204、205、210、215、218,

若采用对分查找在该数组中查找数据200，需要查找的次数是（）若采用顺序查找数据200，需要查找的次数是（），这能说明顺序查找算法比对分查找算法效率高吗？

。

A、1B、2C、3D、4

3.我们育才高中在校生大约有1500人，学号有序排列，若现在利用对分查找来查找你的学号，最多需要查找（）次就能找到你自己。

A、10B、11C、12D、134.[还原高考]医保卡余额查询，小朱设计了某单位医保卡余额查询系统，输入卡号，可以查出该卡号对应的余额。该单位共有n(n<500)名职工，所有职工的医保卡号码和相应的余额等数据存放在数据库文件“company.accdb”的worker表中，程序界面如图所示，左边列表框List1中显示的是全部职工的卡号、姓名和余额，在文本框Text1中输入职工的卡号，单击“查询余额”按钮（Command1）后，如果找到此卡号，则在标签Label5中显示“此人的卡号、姓名和余额”，如果未找到则显示“找不到此卡号，请重新输入”。程序实现代码如下：

Dimkh(1To500)AsLong`kh用于存储卡号

Dimnam(1To500)AsString`nam用于存储职工姓名

Dimye(1To500)AsSingle`ye用于存储医保卡余额

Dimn,i,jAsIntegerPrivateSubForm_Load()

数据库链接与打开代码略

‘从数据库中读取每条记录的卡号、姓名、余额分别存于kh、nam、ye数组中

DoWhilenotrs.EOFn=n+1kh(n)=rs.Fields("卡号")nam(n)=rs.Fields("姓名")ye(n)=rs.Fields("余额")rs.movenextLoop

‘将从数据库中读取出来的数据按余额升序排序Fori=1Ton-1Forj=nToi+1Step-1Ifkh(j)<kh(j-1)Thent=kh(j):kh(j)=kh(j-1):kh(j-1)=tk=nam(j):nam(j)=nam(j-1):nam(j-1)=kp=ye(j):ye(j)=ye(j-1):ye(j-1)=pEndIfNextjNextIList1.AddItem"本单位共有"+Str(n)+"名职工"Fori=1TonList1.AddItemStr(kh(i))+""+nam(i)+""+Str(ye(i))Nexti