3.3.3二分法查找

1、教科版算法与程序设计 （选修） 河北省唐县职业技术教育中心 马丽红,1,3.3.3 二分查找,高中信息技术,3.3.3 二分查找 河北省唐县职业技术教育中心 马丽红,2,3,知识回顾：顺序查找,顺序查找算法查找过程：从数组的第一个元素开始，按顺序依次与Number比较，如果其数与相等，即A(I)= Number ，则显示找到的位置I；否则，执行I=I+1，再重复比较过程。直到IN,则结束查找，说明数组中不存在Number这个数。,程序代码呢？,4,在一个风雨交加的夜晚，从某水库闸房到防洪指挥部的电话线路发生了故障。这是一条长10千米的线路，如何快速找到故障所在的电线杆位置？这条线路上有200多

2、根电线杆，维修线路的工人师傅怎样工作最合理？用之前学过的顺序查找合理么？为什么？,5,想一想,如果使用顺序查找所需要进行的匹配对比次数就很多，所用时间较长，效率低！有没有什么比较高效 的查找方法呢？,我们先来一道最为基础的二分查找题目，理解一下二分查找。 题目 设要在以下有序数列中进行查找： 12 23 34 35 46 55 67 80 99,6,想一想这道题应该怎么查找呢,7,二分查找基础知识： 什么是二分查找 二分查找也叫折半查找，是计算机科学中最基本、最有用的算法之一。它要求被查数据是有序的，否则无法使用二分查找。 二分查找中使用的术语： 目标 Target 你要查找的值 索引 Ind

3、ex 你要查找的当前位置 左、右指示符 Left，Right 我们用来维持查找空间的指标中间指示符 Mid 我们用来应用条件来确定我们应该向左查找还是向右查找的索引,课程新授：,8,二分查找原理 二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。 二分查找一般由三个主要部分组成： 1.预处理 如果集合未排序，则进行排序。 2.二分查找 使用循环或递归在每次比较后将查找空间划分为两半。 3.后处理 在剩余空间中确定可行的候选者。 二分查找是一个效率非常高的算法，它充分利用了元

4、素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。掌握二分查找对于提升代码效率很有帮助。,9,上界,二分查找示意图,下界,下界,上界,以在以下有序数列中查找数据34的位置为例：,先在有序数列中找到中间项A546，判断A5与目标值34的大小,3423,则舍弃左半部分，并把（1+1）作为新的下界，取中间元素的下标3，比较A334与目标值34的大小,34=34，则目标值34就在第3个位置,10,以在以下有序数列中查找数据34的位置为例：,先在有序数列中找到中间项A546，判断A5与目标值34的大小,3423,则舍弃左半部分，并把（1+1）作为新的下界，取中间元素的下标3，

5、比较A334与目标值34的大小,34=34，则目标值34就在第3个位置,为什么中间元素下标取2呢？,11,查找时，设置一个上界和一个下界然后取上下界的中间元素与指定的关键值对比，如图所示。 如果符合，表示找到，查找结束； 如果不符合，再判断关键值落在左半还是右半部； 如果在左半部，则舍弃右半部，保持下界位置不变，将上界设在中间元素的前一个位置，重新查找； 如果在右半部，舍弃左半部，保持上界位置不变，将下界设在中间元素的后一个位置，重新查找。 如此反复进行，若下界大于上界，表示没有元素和关键值相匹配，查找失败。,二分查法流程图,（1）定义Low、Hig和Mid 三个整形变量跟别表示下界、上界和中

6、间元素的下标。 （2）通过外层循环语句依次取出待加密字符串中的一个字符。 （3）初始查找时，设置下界（Low）为数组（aryCode)的第一个元素，上界（Hig)为数组的最后一个元素，并取得中间元素的下标（ Mid). (4)如果中间元素（Mid)和关键值（strChar)相符，则退出内层循环，本次查找结束；如果不相符，判断关键值（strChar）和中间元素（ Mid ）的大小，重设Low或Hig及mid的值。 （5）如果Low= Hig，返回上一步；否则表示没找到，查找结束。,流程解析：,13,14,同学们思考一下，我一直在说要在有序数列里面才能用，那如果在非有序数列中使用会怎么样呢？,15,同学们，了解了二分查找有什么感受呢？,优点：查找速度要比顺序查找效率高，在规模为66536的数组中查找一个数据时，最多经过17次比较就能找到结果。,缺点：只能是在有序数列中进行查找，否则结果是错误的。,总结：,16,课后作业：,设计界面