资源简介

(共31张PPT)
夏日小清新商务通用PPT模板
汇报人：小熊猫
时间：2019.06.07
第二单元
第2节
猜数“魔法”之二分查找
同学们，还记得上一节课我们在魔法学院学到的第一招“魔法”吗？它叫什么？
思考
线性查找！就是从前往后，
按顺序一个一个地找。
线性查找是个特别老实靠谱的“老黄牛”，可是上一节课我们也见识到了它的短板——要是找的数躲在最后面，它就得把10万亿个数从头查到尾，整整要查463天！
博士爷爷又拿出了100张同样的纸牌，这100张纸牌是按照数从小到大有序排列的。游戏中，如果翻到的纸牌数比要找的数大，博士爷爷会提示“大了”，如果翻到的纸牌数比要找的数小，博士爷爷会提示“小了”。
欢欢怎样才能快速地找到要找的纸牌呢？
思考
说一说
思考
你将通过什么算法来快速找到要找的纸牌呢？
请记录游戏中小组同学找到纸牌所用的次数。
我们再次采用缩小问题规模的方法，继续通过10个数来展开探索。
在下面10个数中找出数7。
1至10的中间数是5，7比5大。
将左边数全部移出，查找范围缩小到6至10。
6至10的中间数是8，7比8小。
将右边数全部移出，查找范围缩小到6至7。
继续寻找中间数。
将左边的数移出查找范围。
剩余的最后一个数是7，和目标数相等，查找结束。
寻找有序数列的中间数，然后与目标数进行比较，看是否是查找的目标数，如果不是，可以得知目标数在数列中间数的左边还是右边。每查找一次，就能把查找范围缩小一半，重复执行以上操作，就能快速地找到目标数，这样的查找方法叫二分查找法。
上面我们说过，欢欢的计算机每查找一次需要4微秒，在10万亿个数中查找一个数，用线性查找法，最坏的情况大约需要463天的时间，如果采用二分查找法，最坏的情况又需要多少时间呢？
小知识
小知识
学一学
如果数列是无序的，那么还可以使用二分查找法吗？
1.团团负责整理体育器材，器材室里面有62个柜子。他将柜子编为1至62号，并从1号开始按顺序将运动器材放人柜子，然后关上柜门。这一天，团团忘记把运动器材摆放到多少号柜子了。有什么办法，可以让团团尽可能地减少开门次数来确认运动器材该从哪个柜子继续摆放？
说说你的想法，并请写出你的答案吧。
2.生活中，还有哪些地方可以用到二分查找法呢？
通过本节课的学习，你遇到了哪些困难？是怎么解决的？有哪些收获？和大家分享一下吧！
分享时间，说一说
夏日小清新商务通用PPT模板
汇报人：小熊猫
时间：2019.06.07
归位物品
归位凳子
下
啦
课
！
夏日小清新商务通用PPT模板
汇报人：小熊猫
时间：2019.06.07

展开更多......

收起↑