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

1、折半查找算法及程序实现一、教材剖析教课要点：以图示法方式，演示折半查找算法的基本思想。教课难点：由折半查找算法的思想到程序代码编写的变换，特别是此中要点性语句的编写是教课中的难点。二、学情剖析学生应当已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会碰到的最大问题是：怎样概括总结对分查找解决不一样状况问题的一般规律，基于此，在教课中要踊跃指引学生采纳分解动作、比较迁徙等学习策略。三、教课目的知识与技术：理解对分查找的观点和特色，经过分步分析获取对分查找的解题构造，初步掌握对分查找算法的程序实现。过程与方法：经过剖析多种不一样的可能状况，逐渐概

2、括对分查找的基本思想和方法，确立解题步骤。感情态度与价值观：经过实践体验科学解题的重要性，加强效率意识和全局观点，感觉对分查找算法的魅力，养成一直坚持、不停累积才能获取成功的意志质量。四、教课策略与手段1、教课线索：游戏引领-提出对分查找原理-分析对分查找的算法特色-实践解决问题。2、学习线索：分解问题-概括问题-实践提高，在三个阶段的不停推动中明确对分查找算法，总结规律。五、教课过程1、新课导入（1）热身：游戏（2分钟）找同学上来找一本上千页电话册里面的一个名字。(课程导入我写的不是很详尽，自己设计哦)（2）教师指引：所以我不希望只有他一个人体验这类方便，我们教室里还有一大帮人，其实这类什么

3、不只用于查找电话铺，还能够运用到实质生活中，教室里有这么多人，坦率说，按学校的老方法一个人一个人的数，对全部老师来说都及其费劲，那我们想一想，能否是数数2368，这样好点对吗。不要小瞧这种想法，他实质上是特别棒的，他能把解决问题的时间缩短一半，所以我们提出了这类算法2、新课：第一我们一同来看一看折半查问算法中的“折半”的含义。师：何为折半呢生：减半；打一半的折扣。比如，我手里拿着一根绳索，此刻我们来进行折半试验，第一拿住绳索的两个端点，而后从中点的地点进行对折，这样绳索就缩短为本来长度一半，而后将一半的绳索持续履行与方才相同的操作，使得绳索的长度渐渐的缩短，直到绳索长度短得不可以再进行折半了。

4、师：那什么时候就不可以再折半了呢生：即绳索的两个端点合二为一为止。折半查找算法的思想与绳索折半的过程基真相同。下边我们先经过图示来看看折半查找算法终究是什么教课步骤二：分解对分查找算法（5分钟）假定一个从小到大摆列的数据寄存在一个数组中Data(10)，而查找数据寄存在变量x中。如图1所示，橙色方框的代表的是查问数据x，每个浅兰色方框代表的是数组中的每个元素，框内显示的数据是每个数组元素对应的下标（序号），整排的浅兰色方框就能够当作整个数组，即待查数据表（数组元素表）。xLowHigh图一第一步：就像抓住绳索的两头相同，第一建立两个标志Low、High分别来表记查问区间的低端和高端，即数组元素

5、的下标，如图1所示。师：关于初始查问区间，它们是多少呢生：Low=0，High=10第二步：取区间的中点标志Mid，如图2所示。师：查问区间的中点为多少（这个地方，有的学生可能直接说出下标值，所以要提示学生让中点和两个端点相联系，即用端点表示中点）生：Mid=(Low+High)/2师：中点地点上的数据为何(提示学生数据是放在数组Data中的)生：Data(Mid)LowMidHigh第三步：判断中点地点上的数据Data(Mid)与要查找数x能否相等，如何相等，则找到，并结束查找；假如不相等，就履行第四步。师：这个判断语句怎样写呢生：ifData(Mid)=xthenprint“x找到”结束查

6、找endif第四步：假如不相等，那么对查问区间进行折半操作。师：那怎样折半是从中点处向左边折半仍是向右边折半（这是整个折半查问进行下去的要点所在，所以必定要让学生自己学会判断）因为待找数据表是从小到大摆列的，并且区间中点地点上的数据Date(Mid)也知道，所以，经过Data(Mid)与x的比较，看一看，x比Data(Mid)大仍是小，就能够判断出x落在中间数Data(Mid)的左边仍是右边，进而判断出向左仍是向右折半。师：那么，判断语句怎样写呢生：ifData(Mid)High，停止折半查问。教课步骤四：对各样状况进行概括总结。（1）x与data(mid)的大小比较影响i,j的取值的规律：i

7、的取值规律：ifdata(mid)xthenhigh=mid-1用分支构造实现。(2)持续进行重复查找的条件：lowhigh，用循环构造实现。教课步骤五：建立对分查找的流程图教课步骤六：对分查找算法的初步程序实现。开始lowhighlow1,high10N持续查mid=(low+high)2Ydata(mid)x教师预先设计好Vb窗体，学生只要要在相应的程序体输入代表算法思想的要点语句。附主要程序体：PrivateSubCommand2_Click()DimxAsInteger,midAsInteger,lowAsInteger,highAsIntegerx=Vallow=0:high=10D

8、oWhilelow=highmid=(low+high)2Ifdata(mid)=xThen找到了，是第&mid&个ExitSubEndIfIfdata(mid)data(mid),那么low=mid+1不然high=mid+15、重复上述的3,4步，直到low高出j(或许理解为low=high不建立，所以不可以用fornext,而要用dowhile语句）6、假如有找到x,那履行第4步（1）步后应当输出找到的地点退后出程序，假如不退出，说明x没有找到，所以在相应地点要输出“找不到”。折半查找算法基本思想总结（2分钟）对一有序数据表，第一从初始查找区间开始，拿出区间中点地点上的数据与要查问数据进

9、行比较，若相等，则查找成功，并结束查问；不然，将目前查找区间减小一半。在新的查问区间内，相同拿出区间中点地点上的数据与要查问数据进行比较，若相等，则查问成功，并结束查问，不然将新的查问区间再次减小一半。而后持续采纳相同的方法，直到查找数据成功或许查问区间不可以再折半（即查问失败）为止教课步骤七：评论。评论学生的程序实现状况，并议论或实践问题：假如是降序序列，该怎么样变动程序假如序列元素不是10个，而是100个或更多呢教课步骤八：总结提高。（1）因为对分查找过程中的每次比较都能使得搜寻空间减半，对分查找将不会使用超出log2n次比较来找到目标值。（2）提高对分查找算法的实质意义：同学们可能还没存心识到二分查找是多么高效，那不如假想一下在一个包括一百万个人名的电话簿中找一个名字，二分查找能够让你不超出21次就能找到指定的名字。假如你能够将世界上全部的人依据姓名排序，那