资源描述：
《3.3.3二分法查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《常用算法—查找》学案主讲：李吴松【课程内容标准】1.通过实例，掌握使用顺序查找算法，设计程序解决问题的方法；2.从问题出发，通过相应的科学步骤形成二分查找的算法。 【学习目标】1、认识查找算法的意义 ；2、掌握顺序查找的基本方法，理解并能实现顺序查找的过程；3、理解二分查找的特点及设计思想，并学会用二分查找来解决一些实际问题。【学习重点、难点】1、重点：顺序查找、二分查找的基本方法及注意事项；2、难点：顺序查找、二分查找的实现过程。课程导入：查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查
2、找是常用的基本运算。思考：在日常生活中，用到了哪些查找相关的操作？一、顺序查找的方法和算法实现1问题提出思考：要在本班查找指定姓名同学，解决问题的步骤是什么？2概念提出顺序查找是我们最容易想到，也是最容易实现的一种查找算法，它是将要找的数据与数组中的数据从第一个开始逐一比较，若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。3过程演示活动形式：听教师讲解思考：实现顺序查找的程序流程是什么？思考：代码实现上需要哪些工具？“常用算法—查找”学案第4页，共4页4举例说明操作题1已知数列
3、“24,37,38,39,47,50,53,60,64,70,78,81,87,88,93,96”，编写程序，查找“47”和“50”是否存在于数列中，如果存在，则输出位置，否则输出“未找到”。按照上例的方法，思考程序流程图的设计，填写问号部分的程序，并设计如下的界面。思考程序的实现，与教师同步完成以下程序：OptionBase1PrivateSubCommand1_Click()Dimd()DimmAsIntegerd=Array(24,37,38,39,47,50,53,60,64,70,78,81,8
4、7,88,93,96)Key=Val(Text1.Text)i=1DoWhilei<=16Ifd(i)=KeyThenPrintiExitDoEndIfi=i+1LoopIfi=17ThenPrint"未找到"EndSub5特点分析思考顺序查找的次数：最好：最坏：平均：6小结：如何提高速度？思考：“24,37,38,39,47,50,53,60,64,70,78,81,87,88,93,96”。观察数据的特性，考虑能否更快的找到？“常用算法—查找”学案第4页，共4页二、二分查找的思想和算法实现1问题导入猜
5、数游戏：我们找一位同学随便写一个1-30之间的整数X，大家可以猜一个整数，我可以提示你“大了”，或者“小了”，或者“恭喜你猜中了！”思考使用的方法是什么？2概念提出每次都猜测区间中间点，这样每次都可以把猜测的区间缩小一半。由于30/25<1，因此5次之内就一定可以找出答案。基于这种思想的查找就是二分查找。3算法思想基本思想：取中，比较二分查找的前提是数据已经有序（以递增为例）。把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续二分查找，直到
6、找到待查找的数在数组中的位置或数组已无法二分。4过程演示用图示法来说明二分查找的过程，然后总结出关键语句。演示过程中，将学生分为3组，分别关注low，high，mid的变化过程。“常用算法—查找”学案第4页，共4页归纳mid、low、high的变化过程mid=low=high=5算法实现动手操作，优化上述操作题1的代码，按照二分查找的方式实现。将上述3个关键语句加入程序，并修改相关语句。low=1high=10Key=Val(Text1.Text)DoWhileIfKey=d(m)ThenPrintmEx
7、itDoElseIfKey
