4.3 《非数值计算—二分查找》任务单
学校_________ 班级________ 姓名______________
学习目标
1.了解算法设计中的分治思想。
2.运用二分查找解决实际问题。
3.体验二分查找算法解决实际问题的过程。
游戏体验：谁是“卧底”
游戏规则：从十三张扑克牌中抽取七张，七位同学每人手里一张纸牌，按A—K排序，其中一人手里有一张纸牌做了明显标记，看谁能最快选中“卧底”？
项目 :新品上市，猜定价“赢”棉衣
活动1.寒冬将至，某公司正在推出一款棉衣，为促进棉衣的销售，成功打入市场，现举行猜定价“赢”棉衣的活动。价格范围在1—400元之间。看看哪位同学能以最快的速度猜出棉衣的实际定价。
知识点：二分查找法
二分查找又叫折半查找，将数列有序排列，采用跳跃式查找数据；以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分；每一次比较后都可以将查找区间缩小一半。
二分查找法是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。
在一个有n个元素的有序序列中，利用二分查找大约需要_____次，但是，二分法查找的前提条件是被查找的数据必须是_________。
活动2：根据流程图补充代码并调试运行程序。
x=int(input("请输入要查找的400以内的整数:"))
step=0
flag1=1
flag2=400
while(flag1<=flag2):
mid=(flag1+flag2)//2
step=step+1
if___________:
flag2=__________
elif midflag1=__________
else:
break
print("查找次数为：",step)
input("运行完毕，请按回车键退出...")
拓展练习
1.若提示还是高了，则第三次猜12，依次类推；……。这种每次缩小一半查找范围而达到迅速确定目标的算法称为（ ）。
A.排序法 B.顺序查找法 C.解析法 D.二分查找法
2.二分查找又称折半查找,是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是( )
A.85 78 59 53 19 18
B.67 62 68 4 1 17
C.11 99 4 25 3 39
D.43 71 78 81 6 55
3.小I在阅览室读到了有趣的故事：国王有18枚金币，其中掺进去一枚较轻的假币，要求数学家使用一个没有砝码的天平三次找到假币。如果你是数学家，如何按照要求找到假币？
课后反思(共11张PPT)
4.3 非数值计算
— 二分查找
框架完整·扁平化呈现·绝对专业·超级吸睛
游戏：谁是“卧底”
游戏规则：
七位同学每人手里一张纸牌，按A—K排序，其中一人手里有一张纸牌做了明显标记，看谁能最快选中“卧底”？
项目：猜定价“赢”棉衣
PROJECT PEOFILE
PROJECT PEOFILE
活动1.
寒冬将至，某公司正在推出一款棉衣，为迎接双11购物节，成功打入市场，现举行“猜定价，‘赢’棉衣”的活动。价格范围在1—400元之间。看看哪位同学能以最快的速度猜出棉衣的实际定价。
二分查找/折半查找 p101
二分思想：将数列有序排列，采用跳跃的方式查找数据。
分治策略
将难以直接解决的大问题，分割成较小的同类问题
方法：以递增数列为例，以中点位置元素作为比较对象，若要查找元素值小于该中点元素，将待查找序列缩小为左半部分，否则为右半部分。每次比较后都能将查找区间缩小一半。
找一半
按照顺序找一半，
一比较，舍一半。
继续找一半，
一半又一半，
快速找答案！
左边界
flag1
右边界
flag2
目标数
x
中间数
mid
！！！若中间数mid比目标数x大，则区间变为左半区间，右边界更新
左边界
flag1
右边界
flag2
目标数
x
中间数
mid
！！！若中间数mid比目标数x小，则区间变为右半区间，左边界更新
在有n个元素的有序序列中，利用二分查找大约需要log2n次。
二分查找/折半查找 p101
n = 1000 需要10次
二分思想：将数列有序排列，采用跳跃的方式查找数据。
活动2：补充代码
ABOUT US
活动2.填充代码，调试程序。
x=int(input("请输入要查找的400以内的整数:"))
step=0
flag1=1
flag2=400
while(flag1<=flag2):
mid=(flag1+flag2)//2
step=step+1
if ①:
flag2=②
elif midflag1=③
else:
break
print("查找次数为：",step)
input("运行完毕，请按回车键退出...")
① mid>x
②mid-1
③ mid+1
在有序数组中查找某一特定元素的搜索方法。
查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，重复前面的操作继续从中间元素开始比较。
二分法的使用规则
凡治众如治寡，分数是也。
——《孙子兵法》
课堂小结
