资源简介

第1课 二分查找
第一单元 运用经典算法解决简单问题
学校最近举办了一个比赛，经过激烈角逐产生了决赛名单。学校将入围学生姓名按首字母进行排列，并在公告栏张贴了名单。同学们都非常兴奋，想知道自己是否入围。可是，入围学生数量众多，我们如何才能在名单中快速找到自己的名字呢?
有一排巧克力，里面只有一块加了大量果仁，已知果仁比巧克力重，那么查找这块果仁巧克力的方法有哪些？
从中间掰开，称一称两边的重量。然后从重的一边再继续掰开称重。
可以从最左边开始，一块一块掰开找，总能够找到!
一、二分查找
这种按照一半一半称重的方式，可以快速缩小范围，减少查找时间。这种查找方式就是最初的分半查找。
分半查找常用于查找大量相似物品中有非常明显不同的物品，通过一半一半对物品特征的比较，来确定目标物品的范围。当查找的内容从简单的物品发展到虚拟数据、信息，分半查找这一方式也演化为二分查找法。
如何才能在入围名单中快速找到自己的名字呢？
将名单从正中间分为两部分，将“我”的姓名首字母和中间位置的姓名首字母进行比较，从而确定“我”的名字在名单上半部分还是下半部分。
如果确定名字在上半部分，就继续将名单从中间分开并将“我”的姓名首字母和中间位置的姓名首字母进行对比，确定“我”的名字位置，重复进行这一步骤，直到确定“我”的名字应该在的位置，再确定这个位置是否有“我”的名字，最终得到查找结果。
一、二分查找
二、二分查找算法的描述
（1）找到搜索区域内的中间元素，搜索区域内中间元素是（1+100）÷2=50.5，取其左侧数50。
以从1~100的范围内找到39为例
（2）根据39<50，可以判定39位于50左侧，更新搜索区域为1~49搜索区域内中间元素是（1+49）÷2=25，25不是目标元素，继续查找。
课堂任务一：请学生参照示例继续完成查找过程，并记录每一步的中间值和新的查找范围，直到找到数字39为止。
二、二分查找算法的描述
（3）根据39>25，可以判定39位于25的右侧，更新搜索区域为26~49。搜索区域内中间元素是(26+49)÷2=37.5，取其左侧数37。
（4）根据39>37，判定39位于37的右侧，更新搜索区域为38~49搜索区域内中间元素是(38+49)÷2=43.5，取其左侧数43。
二、二分查找算法的描述
（5）根据39<43，判定39位于43的左侧，更新搜索区域为38~42搜索区域内中间元素是(38+42)÷2=40，继续查找。
（6）根据39<40，判定39位于40的左侧，更新搜索区域为38~39搜索区域内中间元素是(38+39)÷2=38.5，取其左侧数38，继续查找。
（7）根据39>38，判定39位于38的右侧，更新搜索区域为39~39搜索区域内中间元素是(39+39)÷2=39，找到目标元素。
三、二分查找算法的应用
有序数据信息
一分为二
学校的体测数据储存系统可以根据学生姓名或体测数据分别排序，当我们需要查询某一学生的成绩或某一成绩都对应哪些学生时，系统就会使用二分查找算法进行查询。
三、二分查找算法的应用
猜数字游戏
一个人确定一个范围内的目标数字，让其余人猜。每当有人猜一个数字后，确定目标数字的人会告诉大家这次的数是大还是小了。一直重复这个过程直到目标数字被猜出来为止。
课堂任务二：同桌两人合作，在1~50的范围内，使用二分查找法猜出一个设定的目标数字，并记录游戏过程。
三、二分查找算法的应用
在猜数字游戏中，目标范围是1~50，假设目标值是17。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
①1~50范围的中间值是25和26，首先猜数25，告知大了，下次猜数范围缩小为1~24;
②1~24范围的中间值是12和13，猜数12，告知小了，下次猜数范围缩小为13~24;
三、二分查找算法的应用
④13~17范围的中间值是15，猜数15，告知小了，下次猜数范围缩小为16~17。到此，游戏基本结束。
13
14
15
16
17
18
19
20
21
22
23
24
13
14
15
16
17
16
17
③13~24范围的中间值是18和19，猜数18，告知大了，下次猜数范围缩小为13~17;
三、二分查找算法的应用
课堂任务三：
当我们的小区停电时，需要电力工人找到电线的故障位置，然后进行维修，在寻找故障位置的过程中，电力工人通常会用到二分查找法。
假设某段线路一共有200根电线杆，请你描述一下电力工人使用二分查找法排查电线故障点的具体步骤，并分析这种排查方式的优势是什么。
四、课堂小结
1.什么是二分查找？
二分查找算法依照“一分为二”的原理，每次比较中间元素与目标元素，根据比较结果每次将查找范围缩小一半，直到找到目标元素或确定目标元素不在数据范围内。
2.二分查找在生活中的应用。
电力工人排查电线故障、查字典。
五、课后拓展
你能画出前面猜数字游戏的流程图吗？请尝试利用图形化编程软件编写一个小程序。

展开更多......

收起↑