分治算法 怎么工作

切成两半

前面说过，大事要拆成小步骤。这里再往前走一步。
把问题这一大块切成两半，每一半再切成两半，再切成两半。
块就越来越小。

每点一次按钮，每一块都一分为二，块越来越小。

每切一次，要对付的量就少一半。
一大堆让人发愁，一小块就好对付多了。
这和在字典里一半一半地查，是同一种感觉。

块和块不重叠

这里有一点非常重要：切开的两块互不重叠。
左边一堆和右边一堆不会分到同一件衣服，所以一边做过的活儿，另一边不用再做。
两块完全是分开的。

把两块一块块点亮，重叠的部分一点也没有。彼此分开（独立），各自解决也不会撞车。

互不重叠这个性质，比看上去要重要。
块和块不重叠，一边的答案就不会搅乱另一边的答案。
碰上会重叠的问题，情况就不同了，那是另一条路。

解决小块

一直切下去，就会切出再也切不开的小块。
比如一件衣服、一个数。
小到这种程度，用不着多想，马上就能解决。

把最小的块（最底层）一块块点一下，马上就解决了。小到切不开，不用多想就能解决，解决后变成绿色。

不用费劲一口气解决大问题。
一直切到底，再把容易解决的小块一块块解决。
这就把一件难事，变成了许多件容易的事。

往上合并

小答案有了，现在倒过来往上走。
把两个小答案合成一个稍大的答案，再把它们合成更大的答案。
切了几次就合几次，最上面就立起了整个答案。

每点一次，解决好的块就两两合成一块。到最上面，整个答案就完成了。

切的时候往下，合的时候往上。
块和块没有重叠，合起来也干净利落，把左边的答案和右边的答案归到一起就行。
这就是切成两半来征服的方法，也叫分治。

切开，解决，合并

归成一句话：切成两半，把不重叠的块各自解决，再往上合并。
把卡片一半一半分开来排序的方法正是照这个框架做的；在字典里一半一半地查，则是把没有目标的一边整个扔掉、只解决一半的情况。
大东西切开了就变小。

按顺序点这三步，走一圈：切成两半 → 解决小块 → 往上合并。关键是块和块不重叠。

这里的块彼此分得干干净净，解决过的块不用再解决一次。
可要是块和块重叠，同样的东西得一遍遍重新解决，会怎样呢？
下一课我们先看自己重复切分的递归，那个岔路口紧接着就会碰到。