资源简介

(共17张PPT)
二分查找
赣科学技术版五年级下册
第7课
二分查找
了解并掌握二分查找的基本思想
总结出二分查 找与顺序查找的异同
熟练运用二分查找解决实际问题
任务卡
一
试一试
下课啦，小蓝和小红玩起了猜数游戏。小蓝从1到100 之间随机选择了 一个数字让小红猜，其中在小红每次猜出一个数字后，小蓝会给出相应的提 示语。
提示语1:“不是，请重猜!”或“恭喜你，猜对啦!”。
提示语2:“不是，小了!”或“不是，大了!”或“恭喜你，猜对啦!”
假如小蓝心里想的数字是59,小红应该如何设定猜数方案才能用最少的次数猜出59呢
一
试一试
如果按照提示语1玩猜数游戏时，小红则需要把所有可能的数字一一列举出来，如： 第一次：从1开始猜，“不是，请重猜!”;
第二次：2,“不是，请重猜!”;
…
第五十八次：58,“不是，请重猜!”;
第五十九次：59,“恭喜你，猜对啦!”。
综上，小红总共需要猜59次才能猜到小蓝心里想的数字。
这是简单的查找，即我们上节课所学的顺序查找方法。每次猜测都只能排除一个数字。如果小蓝想的是100,那么小红可能需要从1猜到100了。
因此，这种方法是要靠“运气”来决定猜测的次数，即由所猜测的数字在序列范围中的位置所决定。
游戏一
一
试一试
如果按照提示语2玩猜数游戏时，小红可以先猜数值范围内的中间值，再根据小蓝提示的大小关系，选定新的查找范围，这样每次把查找的范围变为了原来的一半左右，直到猜到数字。如：
(1)根据数字范围是1~100,折中猜数字50,发现猜小了，因此要猜的数字在51 和100之间；
(2)根据数字范围是51～100,折中猜数字75,发现猜大了，因此要猜的数字在51和75之间；
(3)根据数字范围是51～75,折中猜数字63,发现猜大了，因此要猜的数字在51和63之间；
(4)根据数字范围是51～63,折中猜数字57,发现猜小了，因此要猜的数字在57和63之间；
(5)根据数字范围是57～63,折中猜数字60,发现猜大了，因此要猜的数字在57和60 之间；
(6)根据数字范围是57～60,折中猜数字58,发现猜小了，因此要猜的数字在58和60之间；
(7)根据数字范围是58～60,折中猜数字59,猜对啦。
游戏二
一
试一试
综上，小红只要猜7次就可以猜到小蓝心里想的数字59。这显然比一个个去试猜的效率要高很多。
游戏二
能够这样猜的原因是，要猜的数字在一个有序的数列中(1～100),并且可以获得大 小关系。这样，根据大小关系逐步缩小猜测范围，最终猜中具体的数字。
二
做一做
综上，小红只要猜7次就可以猜到小蓝心里想的数字59。这显然比一个个去试猜的效率要高很多。
游戏二
能够这样猜的原因是，要猜的数字在一个有序的数列中(1～100),并且可以获得大 小关系。这样，根据大小关系逐步缩小猜测范围，最终猜中具体的数字。
二
试一试
请把你们心中的猜数过程写到书本31页
如果小蓝心里想的数字是77,你能在最快的时间猜出这个数吗
二分查找
二分查找法也称为折半查找法，它充分利用了元素间的次序关系，采用分治策略。它 是一种高效的查找方法，可以明显减少比较次数，提高查找效率。但是，二分查找法查找 的前提条件是被查找的数据必须是有序的(可以从小到大排列，也可以从大到小排列)。
三
学一学
问题
假设某超市出售的糖果有9种不同的价格，分别为5,12,8,20,18,22,16, 30,36。现在要在其中查找价格为30元的糖果所在位置，运用二分查找法应该如何去查找呢
在查找数据时，如果数据已经按照一定的顺序排列好了，也可以利用上述类似的方 法，取大约居于查找范围中间位置的数与要查的数进行比较，然后根据大小调整查找范 围，并最终找到该数据。这种查找数据的方法就是二分查找法。
三
学一学
首先，将这9种糖果的价格按从小到大进行排序，确定待查价格所在的序列范围，将 整个序列一分为二，确定查找的上限、下限与中间值，如图。
(1)将待查价格30与中间值所指位置的价格“18”进行比较，由于30>18,则30必然 在18之后的序列范围中，因此取18的后半段为新的查找范围，如图。
三
学一学
继续将待查价格30与后半段的中间值所指位置的价格“22”进行比较，由于30>22,则 30必然在22之后的序列范围中，因此取22的后半段为新的查找范围，如图。
二分查找的数据是有序的，怎样让一组无序的数据变成有序的，便于我们通过二分查找呢？
练一练
谢谢聆听！
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin

展开更多......

收起↑