C++编程算法：分治算法。

hello各位同学，欢迎来到王老师编程课堂。今天来接触另外一种算法，这个算法的名字叫分治算法。今天带领大家一块来了解一下关于分治算法的基本思想。另外会举一个最简单的二分查找的例子，让大家来体验一下分治算法的奇妙之处。

·首先什么是分治？在生活中经常会提到一个词，比如家长或者老师，或者在看电影电视剧的时候，有人非常经常会提到一个成语叫分而制之。什么意思？本来问问题规模比较复杂，不好解决，一次性解决不好解决怎么办？就分而制之。

·分而制之的算法就叫分治。当然关于分治算法的基本思想也就出来了，它是一个将一个规模为N的问题分解为K个规模较小的子问题，然后分而制之分别解决什么？K个规模较小的子问题，最后子问题全部解决了，大问题就怎么办？就解决了。

但是分治算法这里面有一个限定条件，这些子问题要相互独立，而且要与原问题性质相同，这样才能达到计算机里面分而制之就是分治算法的目的。最终求出这些子问题的解就可以得到原问题的解。所以分治算法的本质是一种分治。标完成程序的算法。

最简单的问题一般情况都可以用二分法来完成。关于分治法的基本步骤，既然要分而制之，第一步就是先分解了，将要解决的问题分解成若干规模较小的同类问题。注意规模较小的子问题，而且是同类问题。

接下来就是求解了，把这些子问题全部求解，当然子问题足够小的时候用最简单的办法都已经可以搞定了。最后分而制之，接下来就是把它合并起来，将原问题的要求按原问题的要求将子问题的解足层合并构成原问题的解，这样就完成了。

所以关于分治算法最关键的步骤是分解、求解和合并这三大步骤。比如先来举一个理论的例子，假设现在有这样一个经典的找尾币的问题，生产线生产了九十九个工件，找劣品了，其中一个工件是劣品，其中比其他九十八个工件质量轻一些，劣品的特征已经出来了，比九十九个里面只有一个是怎么办？比其他九十八个要轻的，现在给的天平至少多少次一定能找到劣品的工件。

先来看一个常规方法，最简单粗暴的方法也称为暴力算法、穷局算法，最简单粗暴的方法是。两个逐个比较，是两两比较，为啥？两两比较只要有一个轻的，那个轻的就是尾臂。

有可能你会发现运气不太好会怎么办？两两比较都一样，前九十八个总共比较了四十九次，因为四十九乘以二九十八，最后剩一个，不用想了，前面九十八个都一样，那是最后剩的那一个肯定就是尾臂。

所以用暴力算法至少需要比较多少次？五十次，当然也有可能会非常幸运，怎么办？凉凉比较拿出来两个，一下子一撑，发现它俩不一样，轻的就是尾臂了。暴力算法就是这样，一个神奇的算法，有可能会很快，也有可能是非常慢，但是要看它的平均速度，平均速度是比较慢，大概需要比较多少次？五十次，平均起来最大次数五十次。

另外第二个方法，来看这个算法就比较有意思了，将九十九个弓箭平均分成三份，每份是三十三个，三十三乘以三，九十九是吧？先比较第一、二份，如果发现平衡，注明列品一定在第三份里边，然后第三份的三十三个再做件事，将列品所在的那一份平均再平均是三份，然后每份十一个，十一乘以三，三十三是吧？

重复第二步什么意思？就那三份里面比较第一、二份，如果发现含平衡，证明列平品在哪一份？列品就在那一份里边是吧？最后这十一个再分成什么？三、三、二，因为十一除以三已经不满足整除了是吧？三份是六个，三份是六个，六个再加二个是八个是吧？错了，这应该是四份，四份加三份，三份是六个，还剩几个？每份十一个是吧？还剩十一个分成三份，确实三四十二，二四得八，八再加三，四四三是吧？

同理一样，如果这两份含一样，尾笔就在这了是吧？尾笔在这了，再分成三份，再比较两个，最终会发现，一定能算出来。而且分支算法会发现按照这样一个规模，每次三分之一的规模，每次三分之一的规模，只需要用几步比较四次就能找到裂屏了。

这是关于这个分支算法举了一个理论的例子，今天写例子，按从最简单的开始学习。比如先来看二分，刚刚这个例子其实是几分？三等分，三分是吧？每次分成三份。

先来看最简单的例子叫二分，二分里面有一个叫二分查找的一个简单查找的案例，来看，请在一个有序递增数数中，它给你有幸提醒了不存在相同元素，一旦存在相同元素，后面会再举更多的案例，就可能会存在左边界查找和右边界查找。

现在这个是一个简单查找，不存在相同元素，采用二分查找找出值x的位置，如果x在数中不存在，请输出负一。如果这个题没有特别指明要用二分可以怎么办？用美举从第一个数开始找，因为它是有序的，从第一个数开始找，找第二个数，找第三个数，找第一个数一个一个比对，最终比对成功了就 ok 了。

但是这里边输入注意看，n有可能是十的六次方，有可能最坏需要比较十的六次方，十的六次方也就是一后面六个零就是一百万次。如果这个数字再大一点，比如十的九次方，按照比赛规定一秒钟能运行时的八十万，暴力算法就一定会怎么办？超时是吧？这时候用二分就可以让超值现象解决了，十的六次方根本就不需要比较十的六次方。

一会来分析一下它到底比较几次，很简单就轻松搞定了，因为它是每次除，每次除，每次除，每次规模都减少到一半，很快规模就会。减少到多少？

·第一行一个整数n代表n组元数的个数，比如八就代表八个数。

·第二行要完成这八个数的输入，比如输了一个一二三四五六七八，第三行要找的整数是x，比如要找五。

·接下来就是输出x在数注中的位置，比如五就在第一个、第二个、第三个、第四个、第五个位置输出五是不是就可以了？

·二分如果是每举算法就是先找一比对一下发现不一样，再找二比对一下发现不一样，再找三比对象发现不一样，再找四比对象不一样，再找五一样了。

·输出中断循环是吧？如果五放在最后就发现一定是从前到后全部遍地的一遍，这叫每举。

·如果是分制算法来分析一下是怎么分制的。先来把这八个数写出来，注意分制一定要先搞清楚边界。

·左右边界起名叫l，右边界起名叫r。什么意思？左边界l现在等于几？等于第一个元素的位置。右边界r现在等于几？等于n，因为是n个数，现在是八个数。这是r左右边界，先定义好了，把它放在左边左右边界，放好了。

·分治算法每次找一半，找一半就找正中间这个me的等于l加r除以二，l是一而二是八，一加八等于九就除以二应该上四，不要余数是吧？第一个、第二个、第三个、第四个，所以现在的m的是谁？是四是吧？这样就完成了第一次查找找amy的，amy的是四，等不等于五？不等于。不等于。这时候怎么办？知道要找的是5，现在找到一个4，5比4怎么办？要大，证明一件事，要找的数没有在前面，这些就不找了。

这种怎么让它不找前面的？将l注意看，移到这个位置，这是新的l，说白了就是如果要找的那个数比当前这个数要大，就去右半部分找，右半部分就是将左边界变成刚刚要找的那个数的位置mid，再加上1，这样规模是不是变成从5、6、7、8去找了？规模是不是降低了一半了？这是第一次查找。

同理按照相同的顺序就可以用循环的思路让mid的这次新的l有了，新的l有了，新的mid再来换一个颜色，新的mid的是谁的？应该就是l等于mid的加一，现在是5，5加8等于13，13除以2等于6，应该找到了谁？就找到了6。

记住再比较mid的是6，但是要找的数是谁？是5，证明右半部分不要了，应该怎么办？找左半部分，r就要更新，r更新为mid，刚刚mid减去谁？减去1，这种发现l和l就怎么办？重叠了，重叠了之后再新的mid，知道就一定等于rl，其中的一个就是5，这种发现mid的终于等于5了，就找到了。输出r、输出l、输出me的是不都可以？当然一般对比的是a、me的就输出me的就可以了。

这样就完成了二分查找的分析。首先一定要注意先定义好左边界l默认等于一，r右边界等于n。接下来这个过程就是循环，什么时候停止？当l小于等于l的时候永远可以进行。但是比如经过这步计算之后如果没找到，也有可能r会再变小或者l会再变大。

不管是r变小还是l变大总是会出现r小于l的情况，循环就可以终止了，就不用找了，没找到吗？就已经没找到了。如果找到了就输出结果。

·第一种情况：如果要找的x比找到的数要大，如果x大于找到的数，证明x在右边，右边就应该在右边找，就应该更新左边键。如果要找的数x小于找到的数，找到的小于找的数，证明x应该在左边，就要更新右边键就可以了。这样每次规模就在减半。

老师举的例子好像八个数最终是找到了三次，如果是按照每举一二三四五是不是找五次？如果举一百个数，假设举一百这个数，然后从一到二到三到四一直找，找九十九一百。如果用没举算法会发现需要找多少次？极有可能要找一百次。

但是如果要用分治，注意看第一次是一百个数砍一半变成多少？五十个数，五十个数再砍一半变成二十五个数，二十五个数再砍一半变成十二个数，十二个数再砍一半变成六个数，六个数再砍一半变成三个数，三个数再砍一半变成两个数或者一个数。

不管怎么样最终的会变成一个数，只需要找第一次、第二次、第三次、第四次、第五次、第六次、第七次，一百个数最多七次就可以找到了。而且一千个数没有想象的多，一千个数其实最多找十次就能找到了。

为什么？因为每次砍半递减的规模其实相当大的，一千除以二变成了五百，五百除以二变成了两百五，两百五除以二变成了一百二十五，一百二十五除以二变成了六十四，六十四除以二变成了三十二，三十二除以二变成了十六，十六除以二变成了八，八除以二变成了四，四再除以二变成了二，二再除以二变成了一，一次、两次、三次、四次、五次、六次、七次、八次、九次，最多十次就剩一个数了。

所以一百个数最多找七次，一千个数只需要最多找几次？十次规模虽然增加了十倍，但是找的数才增加了三次。所以二分查找。它的效率是相当高的。如果真的是要在一千个数里面用暴力算法，有可能要找一千次，而用分制最多找十次，因为它是平均算法。

分制的样例怎么来写？来试试，跟着老师的思路一块来。首先输入是三行输入，第一行是一个整数a，就先写一个int a，然后c in a。接下来第二行是n个数，放到数组里面，要纯组一个数组了。

这个数组多大？人家说数组元素的个数是n小于等于十的六次方。想到这，十的六次方比较大，这个数建议定一个常量叫const int 大n等于十的六次方，十的六次方就是一后面六个零，建议再加个十，这样的数组开的就足够规模大了。

但是以后这样写很容易让你弄混，十的六次方在程序里面也可以这样表述，一、一、六就代表十的六次方，这样创建的数组的规模就是a大n个，大n个就是十到六十万还多十个。

接下来来完成放循环输入n个数，从第一个下标开始用到最后一个下标爱加加，c in ai，这样就完成了第二行的输入。第三行是一个整数x，代表要找的数，再定一个数叫x，然后第三行输入叫c in x，这样就完成了输入了。

接下来就是输了八个数，一二三四五六七八找五，怎么找？这个过程刚刚分析过了，它是一个循环，循环的终止条件是左边界要小于等于右边界，所以来写一个y循环，写上条件l要小于等于r，写到这就知道l是什么的，r是什么的。

要事先先定义好边界边量，int l默认等于一，然后r默认等于n，最后还有一个变量叫me，先不管，先定义好，因为到循环里面再怎么办？更新它这个值，这个值每次计算都不一样，是不是要循环多次？要放到循环题里边，就可以把m的计算一下，等于l加上r除以二，这个就是每次怎么办？二分找中间那个数去判断，找到了得判断看是不是你要的数。

接下来就是判断了if，如果中间这个位置所对应的元素叫amy的，它等于x，或者反过来写，如果要找的数x等于a b 的了，就能证明怎么办？找到了就可以怎么办？直接see alt，直接see alt，mid，不是要找这个数吗？找到了，输出来的位置不就是mid吗？直接see alt，mid就可以了，而且程序已经可以怎么办？结。return零，不用break，只是中断循环而已，而瑞特零程序就结束了，为啥不用break？一会老师会分析。

·还有一种可能就是没找到，没找到就分了两种情况，要找的数x有可能比目前找到的a、me的数要大，证明现在这个数要找的数比现在这个数大，证明这个数应该在右半部分，在右半部分，要找的数在右边，就得更新左边键，注意了，更新在左边键才能继续向右找，更新左边键就是l等于mid，都不是，就从mid加一开始找，这个叫更新自我编程。

·最后一种情况就是另外一个else了，直接写就可以了，或者再写个条件l、c、e、f、x小于是不是也可以？实际上用的三种放循环，三种易复语句不用写最后一个条件了，r就等于me的减一，这句话的意思是要找的数在左边，因为不在，不是这个数也不在左边，不也不在右边是不是就在左边了？

在左边的时候要更新什么？右边键右边界，这样就完成了，完成了一次循环，再次判定l小于等于r是否满足，如果最终都没找到，证明这句话不会输出，程序也不会结束，就怎么办？see out负一，因为没找到的时候人家让说了，如果没找到输出什么？负一，假设把瑞特零现在换成break了，注意了，就算找到了break只是中断循环了，最终是不是还会再输出负一？

所找到了就没必要执行输出负一，直接怎么办？程序结束，这是王老师为啥不用break的原因，来运行下这个程序，先测试一下样例，八个数，要找五，放下输出的五，执行过程就分析的，先求密的找到四，发现四五，要找到五比四大就在右边找，应该更新左边键，l就变成了五，中间数是六，发现这次五又在六的右左边了，就更新右边键，最终l和r都变成了五，me也变成了五，输出me，这种等于五的是吧？

假设现在要找的一个数还是这八个数，找一个九的，这次来看，八个数，要找九就会输出负一，为啥会输出负一？还是一样的过程，先找，先找到四，发现要找的是九，应该在右半部分找，所以就找五六七八，中间数是六，发现还不够，继续向右找，中间数是七，发现还不够继续向右找，现在是八，发现还不够，最终会发现还不够的时候r和l其中有一个一增加就满足不了l小于等于l了，所以循环就结束了，直到循环结束也没有输出，最终输出什么？负一，最终输出负一。

另外关于二维查找，王老师再举一个返利，再举一个返利，比如这次写个八，然后回车，然后要找五，回车。

这次有人说老师五明明在，一三二四八七五六怎么输出的一个负一？注意二分查找，前提是要找的数应该是一个有序递增数列，这样查才能比大小，到底是比它大的数还是比它小的数。要不然像这个例子，一上来比了一个，找了一个，先找到一个四，要找到五，认为在右边，上八七五六里面找。

实际上一三二四八七五六排序了没？没排序。如果要解决这个问题，可以结合结构体，先把它的原始顺序记录着，然后再用结构体排序，那时候再用二分，先要把它变成有序数列，再用二分才可以。

这是关于这个例子，当然这个例子本身就是有序的，提醒的就不要举无序的例子，要不然就给自己带来的麻烦。

以上是今天分值算法的基本思想，另外举了一个简单查找的案例，这个案例还有一个关键点就是所有的数都是不相同的，如果数出现相同的，会发现能找到是因为什么？找到了想找第几个？比如只想找第一个叫首个，还是想找最后一个叫最后一个？这个案例在后面会继续分析。

这节课就先到这，各位同学，拜拜。