选修1算法与程序设计《3.3.3二分法查找》精品优质课教案设计

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

二、重点难点

教学重点：

二分法查找算法的基本思想、特点及程序实现。

教学难点：

使用数组实现二分法查找算法。

三、学习方法及模式

1、自主探究、合作交流等；

2、组内合作，组间竞争；

四、学习内容

（一）新课学习

1、二分法查找基本思想及特点

基本思想：查找时，首先在查找序列的中间位置取出一个元素与目标元素对比，如果目标元素较小，那么就在查找序列的前半部分进行查找，反之，如果目标元素较大，则在查找序列的后半部分进行查找。反复进行这个过程，直至确定目标元素在查找序列中（或者确定不在）。

特点：二分法查找是一种高效的查找方法，但被查找的数据必须是有序的。

2、二分法查找过程

查找时，设置一个下界（Low）和一个上界（Hight），然后取下界到上界之间的中间元素（Middle）与指定的目标元素（Key）比较，如果相符，表示找到，查找结束；若不相符，再判断目标元素是落在中间元素的左半部还是右半部，若落在右半部（即：MiddleKey），则舍弃右半部，保持下界位置不变，将上界设置在中间值的前一个位置（即：Hight=Highe-1），重新查找；如此反复进行，直至查找成功；若下界大于上界，表明待查序列中没有元素和目标元素匹配，查找失败。

温馨提示：对于二分法查找过程理解上有困难的同学，请观看“二分法查找模拟过程”微视频资料。

3、设计算法流程图

根据二分法查找思想及过程，将以下四个处理框放到流程图的合适位置，完成流程图的设计。

4、算法的程序实现

打开二分法查找学生文件夹“工程1﹨工程1.vbp”，分析窗口的设计，读程序代码，再运行程序，感受由算法到程序的转变过程。

（二）探究任务：算法效率

任务1：打开二分法查找学生文件夹下的“工程1﹨工程1.vbp”，先修改程序(L及H的值)，再运行程序，在执行窗体中依次输入目标元素，分析每个目标元素的查找次数，再预测在指定查找范围内查找任意一个数的最大查找次数。最后将分析和预测结果依次填写到任务1的评判表中。单击“评判”按钮，评判结果。

（三）新课学习

1、设疑：在查找序列1-10、1-100或者201-300中，组成查找序列的数是连续的有序的，若查找序列1,7,8,30,100，使用以上算法直接查找8，结果会怎样？

说明：需要查找7次！！！应用连续有序列的查找方法查找不连续的有序列，极大降低查找效率。可以设法为不连续的有序列构建连续的有序列结构。其中，数组的序号是连续有序的。