*****PPT下载/xiazai/二分查找同学们，你们有没有在家里找书、文具或衣服的经历呢？分享一下你找到这些东西的经历吧！●哪一次你找到物品的速度最快？●又是哪一次浪费了很长时间呢？●花费时间的多少与哪些因素有关？信息设备中存储的内容均为数据，在处理这些数据时，查找与排序的操作极为常见，采用正确且高效的算法能够显著提升程序的运行效率。你知道吗？顺序查找?二分查找的工作原理?利用二分查找找到目标?二分查找在生活中的应用目录*我们学习了顺序查找，小清提出了新的疑惑，假如有1000个数据，难道我们要查找1000次吗？有没有更快的查找方法？本节课，就让我们来学习一种效率更高的查找方法——二分查找法。二分查找的原理有没有人从头一页一页翻的?我是根据书的厚度，估着翻一下，然后看一下页码，如果翻过了就往回再翻一下，反复几次就翻到了。从中间翻书难道就是二分查找?我明白了，从头一页一页翻，就像是顺序查找。当老师让同学们把书翻到第50页时，大家都采用什么方法翻书呢？在翻书时，书本的页码总是按顺序从小到大排列。我们可以通过不断翻到中间的页码，然后与目标页码进行比对，缩小查找范围，重复以上的操作，最终找到目标。比如总页数为120页的书籍，要翻到第50页，我们可以先大概翻到中间的位置，如第60页左右；发现比第50大，于是再往前翻，翻到第30页左右，再依次大概翻到第45页、第52页、第48页，最后成功翻到第50页。同理，在有序数列中，要想找到某个特定目标元素，可以通过将查找范围缩小一半，判断目标元素所在的位置，将目标元素所在的范围再次缩小一半，判断目标元素所在的位置……如此重复不断地缩小查找范围，直到找到目标元素。这样的方法就叫作二分查找。探索想一想，如果是一本没按顺序整理的资料，要找到某一页，可不可以用二分查找？用二分查找法查找旗手在用顺序查找法查找旗手的过程中，如果老师给我们的数据是按照从小到大或者从大到小的顺序排列的，我们就可以用二分查找法来简化问题，从而实现快速查找。为了方便演示，我们以10份排好顺序的数据为例，查找身高为148cm的同学。第1步：将10份数据分为两部分，翻开5号体检表，发现其值为144，小于148，因此查找范围缩小至6号至10号体检表，如图所示。第2步：将6号至10号体检表再次分为两个部分，翻开8号体检表，发现其值为147，仍然小于148。查找范围再次缩小至9号至10号体检表，如图所示。第3步：还剩下2份体检表，翻开9号体检表，其值等于目标数据148，查找结束，9号体检表中的身高符合旗手的身高要求，如图所示。二分查找的原理就是在有序数组中，通过不断将查找区间一分为二，比较中间元素与目标数据，再根据比较结果调整查找区间，直至找到目标数据。二分查找的最坏情况是每次查找都未能找到目标数据，每次将搜索范围缩小一半，直到搜索范围为空或只剩下一个元素时才停止。如果有n个元素，每次查找的元素数量除以2，直到元素数量等于1，查找结束。要想将一条纸带均匀分为64个小格子，只需连续对折6次，展开后即可得到64个大小相等的小格子。像二分查找、折纸带这样，将复杂的问题分解为较小的子问题，再分别解决这些子问题，最后将子问题合并解决原问题的策略也叫作分治法。探索使用二分查找，在有100个样本的情况下，最多需要查找多少次呢？当有10万亿个样本时，在最坏的情况下，二分查找只需要43次；而顺序查找在最坏的情况下则需要10000000000000次。你知道吗？顺序查找二分查找的应用04在生活中，我们常常运用二分查找法的原理解决问题。比如，按照拼音查字典、猜数字、排除故障等。7个开关触点可以用夹子夹住，测试电路连通情况。当黄色线路连通，灯泡会被点亮。现在电线1到8段中的某一段出现了故障，小清用二分查找的原理迅速找到了故障位置。他的方法是这样的：第一次连接中间触点D，发现灯泡不亮，于是判定故障一定在1至4段；第二次连接触点B，发现灯泡亮起，说明1、2段正常，故障范围缩小为3、4段；第三次连接触点C，发现灯泡不亮，得出结论：故障在3段。在猜数字游戏中，如果要猜中100以内的一个整数的概率是百分之一，假如利用二分查找的原理来猜，猜中的概率就会大幅提升。猜数字游戏小程序如图1.2.6所示，具体规则是：生成一个1至100的随机数，当猜数字的同学输入答案后，系统会自动判断输入的数是否正确，不正确的话是大了，还是小了，并给