折半查找算法及程序实现教案

对分查找算法及程序实现设计者边楚女单位浙江省瑞安中学教材浙江教育初版社算法与程序设计适用范围选修模块课时一课时联系方式一、设计思想对分查找是计算机科学中的一个基础算法。对于一个基础算法的学习，同样能够让学生在必然的情境下，经历解析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场，同时激活学生的思想，引导学生去研究游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中获得实现，从而使学生成立起对分查找算法形成的科学逻辑结构。二、教材解析本课的课程标准内容：（一）计算机解决问题的基本过程（1）结合实例，经历解析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。（三）算法与问题解决例举C查找、排序与问题解决（2）经过实例，掌握使用数据查找算法设计程序解决问题的方法。本课的《学科授课指导建议》内容：基本要求：1.初步掌握对分查找算法。初步掌握对分查找算法的程序实现。教材内容：第二章算法实例对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时重视是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实责问题的程序实现，本授课方案为第一课时。从《课程标准》和《学科授课指导建议》对本课授课内容的要求来看，要求学生能从问题出发，经过相应的科学步骤形成对分查找的算法。对学生来说，要求经过这一课时的学习能初步掌握或认识对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。三、学情解析学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同样情况问题的一般规律，鉴于此，在授课中要积极引导学生采用分解动作、比较迁移等学习策略。四、授课目的知识与技术：理解对分查找的看法和特色，经过分步解析获得对分查找的解题结构，初步掌握对分查找算法的程序实现。过程与方法：经过解析多种不同样的可能情况，渐渐归纳对分查找的基本思想和方法，确定解题步骤。感神态度与价值观：经过实践体验科学解题的重要性，增强效率意识和全局看法，感觉对分查找算法的魅力，养成向来坚持、不断积累才能获得成功的意志质量。五、重点难点授课重点和难点：分解并理解对分查找的过程。六、授课策略与手段1、授课线索：游戏引领---提出对分查找原理---解析对分查找的算法特色实践解决问题。2、学习线索：分解问题---归纳问题---实践提升，在三个阶段的不断推进中明确对分查找算法，总结规律。七、授课过程1、新课导入（1）热身：游戏（2分钟）教师显现一件特色物品，让一个学生来猜这个物品的价格，其他学生只需要依照这个学生猜出的价格提示“高了”或是“低了”，若是学生能在五次内猜对这个物品的价格，就把这件物品“赠予”给他。（2）谈论：你感觉怎么样猜能够猜的快一点呢？有什么技巧吗？你从这个游戏中间获得什么启示？(3分钟)（3）教师引导：这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个特别经典的算法。引出对分查找的的看法。2、新课：授课步骤一：解析对分查找的原理和思想。（3分钟）（1）对分查找是效率很高的查找方法，但被查找的数据必定是有序的。（2）第一将查找的数与有序数组内处于中间地址的数据比较，若是中间位置上的数与查找的数不同样，依据有序性，即可确定应该在数组的前半部分还是后半部分连续查找。（3）在新确定的范围内，连续按上述方法进行查找，直到获得最后结果。授课步骤二：分解对分查找算法（5分钟）假设：用一个数组d（1to10）来存放升序的元素序列，用i表示查找范围的初步地址的下标，j表示停止地址的下标,mid表示中间地址元素的下标。（1）第一种情况：要找的值在后半部分；以查找键KEY=48为例解析第一次比较：范围d(1)～d(10),mid=(1+10)\2,d(mid)<Key所以能够确定接下来要找的范围是后半部分。比较后i=mid+1第二次比较：范围d(6)～d(10),mid=(6+10)\2,d(mid)<Key所以能够确定接下来要找的范围是后半部分。比较后：i=mid+1第三次比较：范围d(9)～d(10)，mid=(9+10)\2,d(mid)=Key，找到了。思虑：若是要找的是52?i,j,mid分别是多少？

d(1)10d(2)15d(3)17d(4)18d(5)22d(6)27d(7)35d(8)45d(9)48d(10)52d(6)27d(7)35d(8)45d(9)48d(10)52d(9)48d(1052)

imijimidjimidj这也说明当i=j的时候是查找的最后可能次数，这也是停止查找的一个重点条件。授课步骤三：连续分解对分查找算法中包含的其他情况。画一画：请模拟上面的画法,分别画出key=17和key=20的查找表示图。（2）第二种情况：要找的值在前半部分；以查找键KEY=17为例解析：d(1)10id(1)10d(2)15id(2)15mid(3)17d(3)17d17id(4)18d(4)18j(3)18mid(4jd(5)22mi)结果解析：第一次比较后：j=mid-1第二次比较后：i=mid+1第三次比较后：找到了（3）第三种情况：要找的值找不到；以查找键KEY=20为例解析：d(1)10i10id(3)17id(2)15d(1)midd(2)15mid(4)18jd(3)17d(3)17d(4)18d(4)18jd(5)22mid(4)18i,j,midd(6)27d(7)35d(8)45d(9)48d(10）52j结果解析：第一次比较后：j=mid-1第二次比较后：i=mid+1第三次比较后：i=mid+1第四次比较：i=j但是d(mid)≠key,所以找不到。授课步骤四：对各种情况进行归纳总结。（1）Key与d(mid)的大小比较影响i,j的取值的规律：的取值规律：ifd(mid)<keytheni=mid+1的取值规律：ifd(mid)>keythenj=mid-1用分支结构实现。连续进行重复查找的条件：i≤j，用循环结构实现。授课步骤五：成立对分查找的流程图开i1,j10i≤j连续查Nmid=(i+j)\2Y输出“未找计算midd(mid)=key?Y输出找到的YNNimid+1jmid-1结束d(mid)<key?授课步骤六：对分查找算法的初步程序实现。教师早先设计好Vb窗体，学生只需要在相应的程序体输入代表算法思想的重点语句。附主要程序体：PrivateSubCommand2_Click( )DimkeyAsInteger,midAsInteger,iAsInteger,jAsIntegerkey=Val(Text1.Text)i=1:j=10DoWhilei<=jmid=(i+j)\2Ifd(mid)=keyThenText2.Text="

找到了，是第

"&mid&"

个"ExitSubEndIfIfd(mid)<keyTheni=mid+1Elsej=mid-1EndIfLoopText2.Text="

找不到

"EndSub程序说明：1、获得要查找的数据key的值key=Val(Text1.Text)2、i,j

赋初值。

i=1:j=103、求

mid

的值。mid=(i+j)\24、分三种情况，（

1）若是

key=d(mid),

则若是

d(mid)=key

那么Text2.Text="

找到了，在第

"+Str(mid)+"

个"。（2）若是

key>d(mid),

那么

i=mid+1

否则

j=mid+15、重复上述的

3,4

步，直到

i

高出

j(

也许理解为

i<=j

不行立，所以不能够用fornext,而要用dowhile语句）6、若是有找到key,那执行第4步（1）步后应该输出找到的地址退后出程序，若是不退出，说明key没有找到，所以在相应地址要输出“找不到”。授课步骤七：谈论。谈论学生的程序实现情况，并谈论或实践问题：若是是降序序列，该怎么样改动程序？若是序列元素不是10个，而是100个或更多呢？授课步骤八：总结提升。（1）由于对分查找过程中的每次比较都能使得找寻空间减半，对分查找将不会使用高出log2n次比较来找到目标值。（2）提升对分查找算法的实质意义：同学们可能还没有意识到二分查找是多么高效，那不如设想一下在一个包含一百万个人名的电话簿中找一个名字，二分查找能够让你不高出21次就能找