3.3.3 二分法查找 学案 淄博一中 田兆文 【学习目标】 1.理解二分查找算法的基本思想 2.明确二分法查找算法相对于顺序查找算法的优势 3.学会用二分法查找算法解决具体问题 【学习重难点】 重点： 理解二分法查找的算法思想 难点： 用二分法查找算法解决具体问题 【学习环境】 机房，VB6.0 【组织方式】 以价格竞猜为线索的情境教学，小组讨论合作，自主体验探究 【学习方法】 学案导学，小组讨论，合作探究 【导学过程】 【导学一】二分法查找算法及使用条件 中央电视台有一档收视率很高的节目叫“幸运 52”，其中有一个环节，是让选手猜商品的 价格，规则是给出商品的价格范围，主持人根据实际价格和选手报价给出提示：“高了”、 “低了” 、 “正确”。曾经有一个选手，仅仅尝试猜了 3 次，就猜出了实际价格。当时给出的价格范围是 100-300，实际价格是 225。他猜的 3 个数是 200（主持人：低了） 、250（高了） 、225（正确） 。选手的猜数过程：他每次猜的数都是相应范围 的数，这实际上采用的 算法思 想。这种查找算法也叫 ，使用这种查找算法时要求被查找数据必须是 。比较顺序查找与二分法查找：【导学二】二分法查找算法的执行过程 阅读课本 55 页第二段到第六段，完成猜数的具体过程（小组内可讨论） 第一步：将 设为下界， 设为上界，取上下界的中间数 200，根据提示与实际值 225 进行比较，200 比 225 小；舍弃 部分。 第二步：将中间数 右边相邻的数 设为下界，上界还是 ，取上下界的中间数 ，根据提示与实际值 225 进行比较，250 比 225 大；舍弃 部分。 第三步：将中间数 左边相邻的数 设为上界，下界还是 201，取上下界的中间数 225，与实际价格一致，猜中。优点缺点顺序查找二分法查找讨论：采用二分法查找为什么被查找的数据是有序的？【导学三】程序设计界面及设置控件属性值【达标测试】 1.把下面的程序代码补充完整： Private Sub cmdOK_Click()If cmdOK.Caption = “开始“ ThencmdOK.Caption = “正确“cmdSmaller.Enabled = TruecmdBigger.Enabled = TrueintLow = txtLow.TextintHigh = txtHigh.TextintMid = 设置中间值labNumber.Caption = intMidElseMsgBox “猜对了！“, vbOKOnly, “信息提示“cmdOK.Caption = “开始“cmdSmaller.Enabled = FalsecmdBigger.Enabled = FalseEnd If End Sub 2.把下面的程序代码补充完整： Private Sub cmdSmaller_Click()intLow = intMid + 1 重设下界If Then 比较上界、下界大小labNumber.Caption = “猜不到你的数！“cmdOK.Caption = “开始“cmdSmaller.Enabled = FalsecmdBigger.Enabled = FalseElse1.程序中用到哪些控件？ intMid = 设置中间值labNumber.Caption = intMidEnd If End Sub 3.把下面的程序代码补充完整： Private Sub cmdBigger_Click()intHigh = 重设上界If intLow intHigh ThenlabNumber.Caption = “猜不到你的数！“cmdOK.Caption = “开始“cmdSmaller.Enabled = FalsecmdBigger.Enabled = FalseElseintMid = 设置中间值labNumber.Caption = intMidEnd If End Sub导学一：中间 二分法查找 折半查找 有序的导学二： 100 300 左半（小于 200） 200 201 300 250 右半（大于 250） 250 249 要点：数据有序排列才能在与中间数比较后舍弃其中一半。 导学三： Label commandbutton Frame 达标测试 1.（intlow+inthigh）/2 2.intlow inthigh （intlow+inthigh）/2 3.intHigh = intMid - 1 （intlow+inthigh）/2优点缺点顺序查找简单、对数据无要求效率较低二分法查找效率高被查找的数据必须是有序的