算法设计实例教程 课件 第4章 查 找-算法设计实例教程

算法设计实例教程教学分析目录CONCENTS123456789第4章查找第1章数据结构基础第2章基础算法第3章排序算法第5章字符串和高精度运算第6章图论算法第7章动态规划算法第8章计算几何基础第9章高级算法查找也称搜索，搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。第4章查找4.1.1顺序查找的基本概念

顺序查找算法又称顺序搜索算法或者线性搜索算法，是所有查找算法中最基本、最简单的，对应的时间复杂度为O(n)。顺序查找算法适用于绝大多数场景，既可以在有序序列中查找目标元素，也可以在无序序列中查找目标元素。其基本思想是从线性表的第1个元素开始，通过逐个比较表中的关键字，直到找到符合要求的关键字，完成查找，或搜索整个表，没有找到符合要求的关键字，则表示查找失败。但是这种查找方法的效率较低，主要针对数量较少，无规则的数据。如果查找表中的数据已经按顺序排列，则可以使用一种称为二分查找的方法。。4.1顺序查找时间限制：1000ms内存限制：65535KB问题描述输入10个数，要求输出其中的最大值。输入说明测试数据有多组，每组10个数。输出说明对于每组输入,请输出其最大值（有回车）。输入样例102223152657985963240输出样例max=1524.1.2顺序查找的应用举例1：找最大值

算法分析创建一个数组以及创建一个变量max，给变量max赋初值为然后跟数组中每个元素一一进行判断，如果数组中的数比max大那么把这个数赋给max，以此类推，直到查找完数组中的所有元素即可完成查找，停止运算。实现的代码如下：intmain(){intd[10],i,max;for(i=0;i<10;i++)scanf("%d",&d[i]);max=d[0];for(i=1;i<10;i++){if(max<d[i])max=d[i];}printf("max=%d\n",max);return0;}时间限制：1000ms内存限制：32MB问题描述输入一行字符串，计算其中A-Z大写字母出现的次数。输入说明案例可能有多组，每个案例输入为一行字符串。输出说明对每个案例按A-Z的顺序输出其中大写字母出现的次数。输入样例DFJEIWFNQLEF0395823048+_+JDLSFJDLSJFKK4.1.3顺序查找的应用举例2：字母统计

输出样例A:0B:0C:0D:3E:2F:5G:0H:0I:1J:4K:2L:3M:0N:1O:0P:0Q:1R:0S:2T:0U:0V:0W:1X:0Y:0Z:04.1.3顺序查找的应用举例2：字母统计

算法分析该问题的策略就是建立一个长度为26的整型数组用来统计每个字母的出现次数，然后依次遍历字符串中的每一个字符，对字符进行判断，如果该字符是某个字母，就将该字母对应的统计数据加1。代码如下：intmain(){charstr[10000]={0};intcount[26]={0};inti;while(scanf("%s",str)!=EOF){for(i=0;i<strlen(str);i++){if('A'<=str[i]&&str[i]<='Z'){count[str[i]-'A']++;}}for(i=0;i<26;i++){printf("%c:%d\n",'A'+i,count[i]);}}return0;}4.2.1二分查找的基本概念二分查找又称折半查找、二分搜索、折半搜索等，是一种采用了分治策略的查找算法。二分查找只能用于有序线性表的查找。假设在一个长度为n的有序数组中查找一个数字，如果使用顺序查找的方式逐一检查数组中的每个数字，那么需要O（n）的时间复杂度，而如果使用二分查找，时间复杂度可以优化到O（logn）。随着线性表的规模n越大，二分查找在时间性能上的优越性就会越明显。4.2二分查找

4.2.1二分查找的基本概念二分查找的查找策略是：每次将位于线性表中间的数字和目标数字比较。如果中间数字正好等于目标数字，那么就找到了目标数字。如果中间数字大于目标数字，那么下一次查找的时候只需要在线性表的前半部分找，这是因为线性表是排序的，后半部分的数字都大于或等于中间数字，所以一定都大于目标数字，也就没有必要再在后半部分查找。如果中间数字小于目标数字，那么接下来只需要查找线性表的后半部分，这是因为排序数组的前半部分的数字都小于或等于中间数字，所以一定都小于目标数字，也就没有必要再在前半部分查找。从查找的过程可以看出，二分查找是一种递归的过程。由于二分查找算法每次都将查找范围减少一半，对于包含n个元素的列表，用二分查找最多需要log2n步。但是由于二分查找要求待查找的数据必须是线性有序的，对于没有经过排序的数据，可以通过排序算法进行预排序，然后进行二分查找的操作。4.2二分查找

时间限制：1000ms内存限制：65535KB问题描述有n个已经从小到大排序好的数据（不重复），从键盘输入一个数，用二分查找方法，判断target是否在这n个数中。输入说明第1行，数组的长度length第2行，n个整数（int范围内，不重复），中间用空格分隔；第3行，整数target。输出说明如果找到target，输出其位置；否则输出-1。4.2.2二分查找的应用举例1：查找元素x

输入样例10102030405060708090100906-10359122输出样例8-1算法分析使用二分查找算法在一个已排序（升序）的数组中查找一个指定的元素，首先将这个待查找元素与数列中位于中间位置的元素进行比较，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。1.循环方式intsearch_loop(inta[],intsize,inttarget){intleft=0,mid;intright=size-1;while(left<=right){mid=left+(right-left)/2;//定位查找区间的中间元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左边区域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右边区域else//a[mid]就是要查找的元素returnmid;}return-1;//没有找到目标值}4.2.2二分查找的应用举例1：查找元素x

在上面的函数定义中，分别使用了left和right两个变量记住查找的范围。初始情况下left为0，right为数组长度-1，分别指向数组的起始和结束位置。随着查找的推进，每次都根据判断的结果，更新left或者right的值，直到left>right就结束循环。如果直到循环结束都没有找到目标值，则输出-1。2.递归方式由于每次查找的方法是一样的，不一样的仅仅是查找的数组的范围，因此递归是一种很直观的实现方式。用一对整数变量表示目标元素的查找区间的起始和结束位置，并作为参数传递给递归函数。随着查找范围的不断缩小，直到查找区间包含的元素个数少于或等于1个，查找就停止了。实现代码如下：intsearch_recur(inta[],intleft,intright,inttarget){intmid;if(left>right)return-1;//没有找到目标值mid=left+(right-left)/2;//定位查找区间的中间元素if(a[mid]>target)search_recur(a,left,mid-1,target);//递归地查找mid左边区域elseif(a[mid]<target)search_recur(a,mid+1,right,target);//递归地查找mid右边区域else//a[mid]就是要查找的元素returnmid;}4.2.2二分查找的应用举例1：查找元素x

4.2.2二分查找的应用举例1：查找元素

递归的优势就是代码简洁，且能够直观的对应解决问题的思路，但存在的问题是内存消耗太大。main函数实现如下：intmain(){intlength,target,i;while(scanf("%d",&length)!=EOF){for(i=0;i<length;i++)scanf("%d",&a[i]);scanf("%d",&target);printf("%d\n",search_recur(a,0,length-1,target));}return0;}时间限制：1000ms内存限制：65535KB问题描述统计一个数字在一个有序数组中出现的次数。比如输入一个有序数组{1,2,2,2,3,3,3,4,5}和数字2，由于2在数组中出现了3次，因此程序的输出结果为3。输入说明第1行，数组的长度第2行，一个有序数组{1,2,2,2,3,3,3,4,5}第3行，1个待查找的整数target。输出说明如果数组中包含target，则输出其在数组中出现的次数位置；否则输出0。输入样例1012223334552输出样例34.2.3二分查找的应用举例2：统计数字在有序数组中出现的次数

4.2.3二分查找的应用举例2：统计数字在有序数组中出现的次数

算法分析一种直观的方式是使用顺序查找的方式遍历整个数组，只要找到某个元素目标元素target相等，则统计值加1。由于对数组的n个元素都进行了一次检查，所以该算法的时间复杂度为O(n)。使用二分查找在数组中查找元素target在数组中的位置，由于数组是有序的，因此所有相等的值在数组中的位置是连续的，因此可以继续在该位置的前后查找与target相等的元素。前面已经分析过，二分查找能够快速的缩小查找的范围，将算法的时间复杂度降低到O(logn)。使用二分查找法进行数字统计的函数实现如下：intnum(inta[],intsize,inttarget){intleft=0,right=size-1,mid,sum=0;inti;while(left<=right){mid=left+(right-left)/2;//定位查找区间的中间元素if(a[mid]>target)right=mid-1;//待查元素在mid元素的左边区域elseif(a[mid]<target)left=mid+1;//待查找元素在mid元素的右边区域else//a[mid]就是要查找的元素{sum=1;//找到了一个目标元素break;}}for(i=mid+1;i<size&&a[i]==target;i++)//向左统计sum++;for(i=mid-1;i>0&&a[i]==target;i--)//向右统计sum++;returnsum;4.2.3二分查找的应用举例2：统计数字在有序数组中出现的次数

在顺序查找和二分查找中，算法要处理的数据以线性表的形式表示。在线性表中，数据元素之间是线性关系，每个数据元素只有一个直接前驱和一个直接后继。但是在图中，任意两个数据元素之间都可能存在直接的关系，通常用节点表示数据元素，用连接两个节点的边表示数据元素之间的关系。图的搜索算法通常用来解决基于状态空间的搜索问题。所谓状态就是为了区分不同事物而引入的一组数据元组，如X=[x1,x2,x3...xn]，其中每一个元素xi被称为状态分量。首先把问题表示转化为一个由多个状态组成的集合，如果可以通过一些定义好的运算使得某个状态跳转到下一个状态，那么这两个状态之间就形成了一个关联关系。所有的状态，以及状态之间的关联关系就形成了一个拓扑图。解题的过程就是对图的搜索。对一个图进行搜索意味着从图中的一个节点开始，按照某种特定的顺序依次遍历图中的边，从而找到一条从起始节点到目标节点的路径，或是遍历图中所有的节点，找到符合检索要求的节点。按照搜索顺序的不同，可以将搜索算法分为广度优先算法和深度优先搜索。4.3图的搜索

DFS（DepthFirstSearch），即深度优先搜索。其搜索策略是：从图中某节点v出发，沿着一条路径一直搜索下去，当无法搜索时，回退到刚刚访问过的节点。具体说来包括以下几个步骤：4.3.1DFS的基本概念

（1）初始化图中的所有节点，将它们都标记为未被访问。（2）从图中的某个节点v出发，访问v并标记其已被访问。（3）依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复步骤2～3），这一过程一直进行到已发现从出发节点可达的所有节点为止。（4）如果当前已经没有未被访问的邻接节点时，则回退到上一步刚刚访问过的节点，继续重复步骤2~3。按照深度优先搜索，当搜索到某一步时，发现原先的选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术被称为回溯法，而满足回溯条件的某个状态被称为“回溯点”。4.3.1DFS的基本概念

按照深度优先搜索算法遍历图中的节点，我们会发现后被访问的节点，其邻接点先被访问，这是典型的后来者先服务，可以借助于栈的结构来实现。由于递归本身就是使用栈实现的，因此使用递归的方法更方便。深度优先搜索算法可以用以下伪代码来表示：voidDFS(GraphG,nodev){nodew;visit(v);visited[v]=True;for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])DFS(G,w);}从图G中的某一个节点v开始，首先访问节点v，并将v的状态设置为已访问。随后依次对v的所有邻接节点w进行遍历，如果w是一个未被访问过的节点，则继续使用深度优先搜索算法以w为出发节点进行搜索。由于算法是递归调用的，当v的某个邻接节点w访问不下去的时候，函数返回到v，继续对v的下一个邻接节点使用DFS展开搜索。。4.3.1DFS的基本概念

下面以下图为例模拟深度优先搜索算法的搜索路线。4.3.1DFS的基本概念

图4-1二叉树树是图的一种特殊形式，是连通且没有回路的图。图中所示的是一棵二叉树，即每个父节点最多只有两个子节点，其中一个是左子节点，一个是右子节点。现在我们要使用深度优先算法遍历树中的每一个节点，那么节点编号所组成的序列就是遍历的顺序。假设我们规定对每一个节点来说，先访问其左子节点，后访问其右子节点。按照深度优先搜索算法：（1）从根节点1开始（2）先访问1的左子节点2，然后以递归的方式遍历以2为根节点的子树，以此类推，得到1→2→4→7遍历序列。（3）到达节点7后，发现其没有左子节点，也没有右子节点，于是返回到节点4，节点4的也没有右子节点，于是继续向上返回到节点2，节点2有右子节点，于是访问节点5，更新遍历序列为1→2→4→7→5。（4）节点5既没有左子节点，也没有右子节点，于是返回到其父节点2。此时节点2完成了其所有子节点的遍历，于是继续向上返回到节点1。（5）此时节点1已完成了左节点的遍历，继续访问其右节点3，更新遍历序列为1→2→4→7→5→3。节点3没有左子节点，于是访问其右节点6，更新遍历序列为1→2→4→7→5→3→6。（6）节点6先访问左子节点8，由于节点8没有子节点，于是完成访问后返回节点6，然后访问节点6的右子节点9，更新遍历序列为1→2→4→7→5→3→6→8→9。同样，由于节点9也没有子节点，于是完成访问后返回节点6。（7）节点6已完成其所有子节点的访问，于是返回节点3，同样，节点3也完成了所有子节点的访问，于是返回节点1，完成所有节点的遍历和递归访问。得到结论，基于深度优先搜索算法遍历该树的所有节点时，访问序列为：1→2→4→7→5→3→6→8→9。4.3.1DFS的基本概念

BFS（BreadthFirstSearch），即广度优先搜索。其搜索策略是：从起点开始，对与其邻接的所有节点都访问一边，然后依次从这些已经访问过的邻接点出发，再对它们的邻接点进行访问。具体说来包括以下几个步骤：4.3.2BFS的基本概念

（1）初始化所有节点均未被访问，并初始化一个空队列。（2）从图中的某个节点v出发，访问v并标记其已被访问，将v入队列。（3）如果队列非空，则继续执行，否则算法结束。（4）将队头元素v移出队列，依次访问v的所有未被访问的邻接点，标记已被访问并将它们加入队的尾部。转向步骤3。按照广度优先搜索算法遍历图中的节点，我们会发现每次都是从队列的头部拿出一个节点进行扩展，而新扩展出的节点都是加到队列的尾部，因此所有的节点按照先进先出的顺序被访问，可以借助于队列的结构来实现。队列是一种先进先出的数据结构，你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。4.3.2BFS的基本概念

广度优先搜索算法可以用以下伪代码来表示：voidBFS(GraphG,nodev){初始化一个空队列queue;将nodev加入queue头部；while(queue不为空){nodev=queue_front();visited[v]=True；pop_front(queue);for(w=FirstNeighbor(G,v);w!=null;w=NextNeighbor(G,v))if(!visited[w])将节点w加入queue尾部；}}下面依然以图4-1为例模拟广度优先搜索算法的搜索路线。按照广度优先搜索算法：（1）队列初始条件下为空queue={}；（2）从根节点1开始，将节点1放入队列，得到队列为{1}。（3）将队列中的第一个元素1取出来，将其标记为已访问，并将1的所有未访问的邻接节点放入队列的尾部，队列更新为{2，3}，访问序列为1。（4）将队列中的第一个元素2取出来，将其标记为已访问，并将2的所有未访问的邻接节点放入队列的尾部，队列更新为{3，4，5}，访问序列为1→2。（5）将队列中的第一个元素3取出来，将其标记为已访问，并将3的所有未访问的邻接节点放入队列的尾部，队列更新为{4，5，6}，访问序列为1→2→3。（6）将队列中的第一个元素4取出来，将其标记为已访问，并将4的所有未访问的邻接节点放入队列的尾部，队列更新为{5，6，7}，访问序列为1→2→3→4。4.3.2BFS的基本概念

（7）将队列中的第一个元素5取出来，将其标记为已访问，由于5没有未访问的邻接节点，于是队列更新为{6，7}，访问序列为1→2→3→4→5。（8）将队列中的第一个元素6取出来，将其标记为已访问，并将6的所有未访问的邻接节点放入队列的尾部，队列更新为{7，8，9}，访问序列为1→2→3→4→5→6。（9）将队列中的第一个元素7取出来，将其标记为已访问，由于7没有未访问的邻接节点，队列更新为{8，9}，访问序列为1→2→3→4→5→6→7。（10）将队列中的第一个元素8取出来，将其标记为已访问，由于8没有未访问的邻接节点，队列更新为{9}，访问序列为1→2→3→4→5→6→7→8。（11）将队列中的第一个元素9取出来，将其标记为已访问，由于9没有未访问的邻接节点，队列更新为{}，访问序列为1→2→3→4→5→6→7→8→9。（12）由于队列为空，结束循环，搜索结束，最终得到的树的广度优先搜索序列为1→2→3→4→5→6→7→8→94.3.2BFS的基本概念

时间限制：1000ms内存限制：32MB问题描述输入一个包含n个节点的树，节点编号依次为0、1...n-1，以及一个包含n-1条无向边的edges列表，其中edges[i]=[a,b]表示节点a和节点b中存在一条无向边。当选择其中任何一个节点作为根节点时，都可形成一棵高度为h的树。在所有可能的树中，具有最小高度的树被称为最小高度树。要求找到所有的最小高度树，并依次输出它们的根节点编号。输入说明一个整数n，代表树的节点数。一个二维矩阵edges，表示树的边输出说明所有最小高度树的根节点编号。输入样例n=4edges=[[1,0],[1,2],[1,3]]输出样例[1]4.3.3DFS与BFS的应用举例1：最小高度树

算法分析以样例输入为例，该树包括4个节点，3条边，当我们选择其中任何一个节点作为树根时，都可以相应构造出一棵树，树的结构如下：4.3.3DFS与BFS的应用举例1：最小高度树

图4-2不同高度的树其中最小高度树是以节点1为根的树，树高为1。由于树的连通性且没有环，任何一个节点都可以作为树根，从而形成一棵树。直观的解决办法是依次对每一个可能形成的树使用DFS算法，然后计算树中每个节点的高度，并将其中最大值作为树的高度。但是这种算法的时间复杂度太高了，是O(n2)。通过观察树的结构，我们发现如果将度为1的节点作为叶子节点的话，那么这棵树的高度会最小。因此，我们可以使用类似剥洋葱的方法，一层一层的删掉叶子节点，最后剩下一个或两个节点就是我们要找的最小高度的根节点。4.3.3DFS与BFS的应用举例1：最小高度树

算法设计如下：1、如果n==1，则直接返回[0]，这是因为当树只包含一个节点时，树的高度为0，节点0就是这个树的根。2、如果n==2，则返回[0,1]，这是因为当树包含两个节点时，树的高度为1，节点0和节点1都可以是最小高度树的根。3、创建一个空队列queue；4、遍历edges[][]数组，计算每个节点连接到其他节点的边数，并将所有度为1的节点加入队列queue中。5、将队列queue中的节点依次删除，同时图中将其他连接到该节点的节点的度减1。6、当减1后的节点的度也变成1，就作为新的要删除的节点加入队列；7、循环执行步骤3和步骤4，直到图中所有的节点要么被删除了，要么已在队列中，此时队列中还未被删除的节点就是最小高度树的根节点。4.3.3DFS与BFS的应用举例1：最小高度树

时间限制：1000ms内存限制：32MB问题描述：现在有一个容量为S毫升的瓶子，里面正好装满了水，还有两个空杯子A和B，它们的容量分别是N毫升和M毫升，且S==N+M。现在想将瓶子里的水平均分成两份，但可惜的是无论是瓶子还是杯子都没有刻度，聪明的你能否利用它们三个之间相互倒水的方式将水平分呢？如果能请输出最少的倒水次数，如果不能输出No。输入说明输入一行包括三个以空格分隔的整数S,N,M，分别代表水的体积和两个杯子的容量。其中，0<s<101,N>0,M>0输出说明如果能平分的话请输出最少要倒的次数，否则输出No。输入样例1743输出样例1No输入样例2413输出样例23。4.3.4DFS与BFS的应用举例2：水壶问题

4.3.4DFS与BFS的应用举例2：水壶问题

算法分析：我们可以用