3.3.3二分法查找.doc

二分法查找导学案1、 课前自主学习自主阅读课本PP页，完成自主检测。1、 什么是二分法查找？ 2、 二分法查找的要求是什么？ 3、 如何利用二分法查找数据？ 4、与同学交流，讨论后，请列举一两个生活中用二分法查找的案例。2、 体验猜数字游戏1、 创设情景，激发兴趣，导入课题。大家知道中央电视台有一档收视率很高的节目叫“幸运52”，其中有一个环节，是让选手猜商品的价格，规则是给出商品的价格范围，主持人根据实际价格和选手报价给出提示：“高了”、“低了”、“正确”。曾经有一个选手，仅仅尝试猜了3次，就猜出了实际价格。当时给出的价格范围是100-300，实际价格是225。他猜的3个数是200（主持人：低了）、250（高了）、225（正确）。我们仔细分析这个选手的猜数过程，可以发现每次猜的数都是相应范围中间的数，这实际上采用了“二分法查找”的算法思想。【任务一】启动VB，选“现存”-“桌面” “二分法查找练习”文件夹下的的计算机猜数.vbp文件，体验游戏。 【思考讨论，小组探究】提出问题1：计算机猜数游戏中究竟是怎样查找的？ 是通过什么方法快速的猜出数字呢？提出问题2： 如果没有顺序则能否进行二分查找？这说明二分查找对待查数据序列有什么要求？3、 教师讲解分析从被猜商品的价格范围100-300，将100设为下界，300设为上界，取上下界的中间元素200与实际值225进行比较，200比225小；将200右边相邻的数201设为下界，上界还是300，取上下界的中间元素250与225进行比较，250比225大；将249作为上界，下界还是201，取上下界的中间元素225与225比较，正确，猜中。【思考讨论，小组探究】提出问题3： 请根据二分法算法的思想，将流程图补充完整【任务二】启动VB，打开桌面上的查找数字.vbp文件，尝试修改源代码。 要求：完善程序 ，要求实现8个数据元素的逐一赋值，并查找输入的关键值在不在数组中?Private Sub Form_Click()Dim i, low, high, mid, key, a(7) As IntegerFor i = 0 To 7 for 循环为数组赋值 a(i) = InputBox(请依次输入8个数组元素)Next ikey = 70 设置关键值，设置下界和上界的初始值low = 0: high = 7Do While 继续查找的条件是什么? mid = 如何计算中间值？ If a(mid) = key Then Print 查找成功 如果中间值等于关键值，则找到了，直接退出Do循环 Exit Do Else If keya(mid) Then 否则判断关键值在左半部还是右半部 low = 如果关键值大于中间元素，则落在右半部，应重新设置什么？Else high = 否则，则落在左半部，应重新设置什么？ End If End If Loop 再次查找 If low high Then Print 查找不成功 End IfEnd Sub举一反三想一想：用拼音法查字典，如何快速定位到汉字拼音首字母所在的位置？ 小组合作，利用以下字母表，分别观察用这种逐步二分的方法定位到字母C和字母S时low,high和mid的变化情况，回答以下问题 ：highmidlowhigh【思考讨论，小组探究】提出问题4：1.如果key a(m) Then 目标和关键值不匹配,重新设置下界或上界 Low = m + 1 落在右半部分 Else High = m - 1 落在左半部分 End If End If Loop If Low = High Then