选修1算法与程序设计《3.3.3二分法查找》公开课教案下载

选修1算法与程序设计《3.3.3二分法查找》公开课教案优质课下载

【学情分析】学习过顺序查找、冒泡排序，对数据查找和有序有了解。

【教学重点与难点】

重点：二分查找的原理

难点：查找结束的条件

【设计思路】

1、教学线索：游戏引领---提出二分查找思想---?解析二分查找的算法特征---实践解决问题。?

2、学习线索：分解问题---归纳问题---实践提升，在三个阶段的不断推进中明确对分查找算法，总结规律。

【教学过程】

【导入】六一活动，价格竞猜，猜中三次有奖

（学生）猜中的同学解释猜测过程。

（教师）揭示课题，明确前提条件——数据有序。

{设计意图}游戏方式初步体会二分查找思想

【解析】二分查找的原理

因为有序，每次在一半的位置进行查找比较。

找位置：设置下界low、上界high，确定中间位middle=(low high)﹨2。

注意：奇数个数，折半以后是整数；偶数个数，折半以后取整。故除法符号用整除﹨。

以长度为10的一维数组为例，详细分析二分查找的思路。

初始：low=0,high=9，确定middle=（low+high）﹨2=4

值比较：若SearchValue=X(middle)，则表示“找到”，查找结束。否则，判断落在哪半个区域，继续找；

若落在左半部，则舍弃右半部，确定新的上界，即high=middle-1，重新查找；

若落在右半部，则舍弃左半部，确定新的下界，即low=low+1，重新查找；

如此反复进行。

（演示过程）

找到了，查找结束；但所有数据都找完，查找失败，也要结束。

从图示可见，结束条件为，high