分治法和减治法的区别。
分治法是把一个大问题划分为若干个子问题，分别求解各个子问题，然后再把子问题的解进行合并得到原问题的解。
减治法同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。
所以，严格的说，减治法应该是一种退化了的分治法，时间复杂性一般是O(log2 n)。
减治法在将原问题分解为若干个子问题后，利用了规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间的关系，这种关系通常表现为：
（1）原问题的解只存在于其中一个较小规模的子问题中；
（2）原问题的解与其中一个较小规模的解之间存在某种对应关系
查找问题中的减治法
折半查找
折半查找利用了记录按关键码有序的特点，其基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。
- 剑指 Offer 53 - II. 0～n-1中缺失的数字 - 简单 代码
- 668. 乘法表中第k小的数 - 困难 代码
二叉查找树
二叉查找树又称二叉排序树，是具有以下性质的二叉树；
（1）若它的左子树不空，则左子树上所有节点的值均小于根节点的值
（2）若它的右子树不空，则右子树上所有节点的值均大于根节点的值
（3）它的左右子树也都是二叉排序树
在二叉排序树root中查找给定值k的过程是：
（1）若root是空树，则查找失败
（2）若k=根节点的值，则查找成功
（3）否则，若k<根节点的值，则在root的左子树上查找
（4）否则，在root的右子树上查找
讲这个感觉没啥用，二叉查找树比较麻烦的是如何构建这颗树吧。而且其实折半查找就是用数组表示了二叉查找树结构。这个就不找题做了，没想到有什么场景。
排序问题中的减治法
堆排序
定义：堆（heap）是具有下列性质的完全二叉树：每个节点的值都小于或等于其左右孩子节点的值（小根堆）；或者每个节点的值都大于或等于其左右孩子节点的值（大根堆）。如果将具有个节点的堆按层序从1开始编号，则节点之间满足如下关系：
(1)ki <= k(2i) 且 ki <= k(2i+1)
(2)ki >= k(2i) 且 ki >= k(2i+1)
1<=i<=n/2
这个定义其实说明了用数组存储堆的话，数据的特征。
堆排序是利用堆的特性进行排序的方法，其基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。
堆调整问题是关键，主要有筛选调整法和插入法调整。
筛选法调整堆要解决的关键问题是：在一个完全二叉树中，根节点的左右子树均是堆，如何调整根节点，使整个完全二叉树成为一个堆？
方法为：根节点和左右子树的根节点比较，将最大值和和根节点进行交换，直到所有子树均为堆或者调整的节点到了叶子节点。
插入法调整堆要解决的问题是：在堆中插入一个节点，如何调整被插入的节点，使整个完全二叉树仍然是一个堆？
方法为：在末尾插入节点，将该节点与双亲节点进行比较，如果不满足堆条件，将该节点和根节点进行交换，重复执行这个过程，直到节点小于双亲节点或者到了根节点。
堆排序需要完成两个操作：
1）将数组调整为堆：
- 方法1：从最后一个非叶子节点开始，比较该节点和子节点的值进行调整，调整完成后，比较倒数第二个非叶子节点，持续这个过程，直到根节点。第一个叶子节点，一定是序列长度/2，所以第一个非叶子节点的索引就是arr.length / 2 -1。参考
- 方法2：使用插入法，按照数组顺序，一个一个插入
2）排序：将根节点和最后一个叶子节点对调，然后使用筛选法将剩余的元素重新构建成堆
- 面试题 17.14. 最小K个数 - 中等 代码
选择问题
设无序序列T=(r1,r2,……,rn)，T的第k(1<=k<=n)小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找T的第k小元素的问题称为选择问题。特别地，将寻找第n/2小元素的问题称为中值问题。
这种类型的题可以借鉴快速排序的划分过程。每次划分，会确定出一个轴值，判断轴值所在位置比k大还是小，从而减小范围。使用这种方案时间复杂度为O(n)。
这种类型的题和上面最小K个数的区别在于，一个选择出一个数值，一个需要返回一定范围。
- 215. 数组中的第K个最大元素 - 中等 代码
组合问题中的减治法
淘汰赛冠军问题
假设有n=2^k个选手进行经济淘汰赛，最后决出冠军的选手，用函数bool Comp(string mem1, string mem2)
模拟两位选手的比赛，若mem1获胜则函数Comp返回TRUE，否则函数Comp返回FALSE，并假定可以在常数时间内完成函数Comp的执行，如何模拟淘汰比赛过程？要求时间复杂度为O(n)。
这个思路比较简单，将所有用户二等分，两段的起始索引为0和n/2，让0与n/2比较，赢的放前面。一直遍历到n/2-1，前n/2都是胜利的人。再次二等分，做这种循环，最终第0个人是最终胜利者。
这种问题很难找到对应的练习题，因为这种题有个特性，就是两个数据只能存活一个。而且这道题编写也不是很困难，就不做了，但是大家如果有合适的题可以提供给我。
假币问题
在n枚外观相同的硬币中，有一枚是假币，并且已知假币教轻。可以通过一架没有刻度的天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个搞笑的算法来检测出这枚假币。
因为知道哪个假币教轻，所以计算思路比较简单
方案1：分成两堆，进行比较，教轻的一堆再分成两堆，直至找到最轻的硬币，时间复杂度为O(log2 n)
方案2：分成三堆，如果比较两堆重量一样，则第三堆有假币；如果比较的两堆有一堆教轻，则该堆有假币。重复这个过程，直至找到最轻的硬币，时间复杂度为O(log3 n)
现在让我们把问题复杂化，如果有8枚硬币(a b c d e f g h)，假币重量教轻还是较重，如何处理？
解决这个问题需要使用判定树，具体细节留给大家自己思考。
假币问题乐扣上也没有找到相应的题目，毕竟有值但是又不让用的题比较难出，大家也比较难接受，不过在实际生活中，这个还是很有用的。
总结
减治法和分治法是相似的，只不过减治法每次执行规模会减半。本篇里需要重点关注的有
查找问题：折半查找
排序问题：堆排序、选择问题
其中折半查找大家可能都觉得很容易，其实只是思想理解起来容易，真正编码的时候，涉及到很多边界条件，我用折半查找面试过很多人，能写的完美的比较少。
堆排序是必然要掌握的，关于堆的相关习题太多，大家一定要自己做一番。
最后
大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）
往期文章回顾：
算法
技术
- 浅谈微服务
- TCP性能优化
- 限流实现1
- Redis实现分布式锁
- Golang源码BUG追查
- 事务原子性、一致性、持久性的实现原理
- CDN请求过程详解
- 记博客服务被压垮的历程
- 常用缓存技巧
- 如何高效对接第三方支付
- Gin框架简洁版
- InnoDB锁与事务简析
读书笔记
思考
