分治法和减治法的区别。

分治法是把一个大问题划分为若干个子问题，分别求解各个子问题，然后再把子问题的解进行合并得到原问题的解。

减治法同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。

所以，严格的说，减治法应该是一种退化了的分治法，时间复杂性一般是O(log2 n)。

减治法在将原问题分解为若干个子问题后，利用了规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间的关系，这种关系通常表现为：

（1）原问题的解只存在于其中一个较小规模的子问题中；

（2）原问题的解与其中一个较小规模的解之间存在某种对应关系

1查找问题中的减治法

1.1折半查找

折半查找利用了记录按关键码有序的特点，其基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

1. 剑指 Offer 53 - II. 0～n-1中缺失的数字https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/ - 简单 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/lossnumber.go
2. 668. 乘法表中第k小的数https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/ - 困难 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/kthsmallestnumberinmultiplicationtable.go

1.2二叉查找树

二叉查找树又称二叉排序树，是具有以下性质的二叉树；

（1）若它的左子树不空，则左子树上所有节点的值均小于根节点的值

（2）若它的右子树不空，则右子树上所有节点的值均大于根节点的值

（3）它的左右子树也都是二叉排序树

在二叉排序树root中查找给定值k的过程是：

（1）若root是空树，则查找失败

（2）若k=根节点的值，则查找成功

（3）否则，若k<根节点的值，则在root的左子树上查找

（4）否则，在root的右子树上查找

讲这个感觉没啥用，二叉查找树比较麻烦的是如何构建这颗树吧。而且其实折半查找就是用数组表示了二叉查找树结构。这个就不找题做了，没想到有什么场景。

2.排序问题中的减治法

2.1堆排序

定义：堆（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。参考https://blog.csdn.net/qq_28063811/article/details/93034625
• 方法2：使用插入法，按照数组顺序，一个一个插入

2）排序：将根节点和最后一个叶子节点对调，然后使用筛选法将剩余的元素重新构建成堆

1. 面试题 17.14. 最小K个数https://leetcode-cn.com/problems/smallest-k-lcci/ - 中等 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/smallestk.go

2.2选择问题

设无序序列T=(r1,r2,……,rn)，T的第k(1<=k<=n)小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找T的第k小元素的问题称为选择问题。特别地，将寻找第n/2小元素的问题称为中值问题。

这种类型的题可以借鉴快速排序的划分过程。每次划分，会确定出一个轴值，判断轴值所在位置比k大还是小，从而减小范围。使用这种方案时间复杂度为O(n)。

这种类型的题和上面最小K个数的区别在于，一个选择出一个数值，一个需要返回一定范围。

1. 215. 数组中的第K个最大元素https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ - 中等 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/kthlargestelement.go

3.组合问题中的减治法

3.1淘汰赛冠军问题

假设有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个人是最终胜利者。

这种问题很难找到对应的练习题，因为这种题有个特性，就是两个数据只能存活一个。而且这道题编写也不是很困难，就不做了，但是大家如果有合适的题可以提供给我。

3.2假币问题

在n枚外观相同的硬币中，有一枚是假币，并且已知假币教轻。可以通过一架没有刻度的天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个搞笑的算法来检测出这枚假币。

因为知道哪个假币教轻，所以计算思路比较简单

方案1：分成两堆，进行比较，教轻的一堆再分成两堆，直至找到最轻的硬币，时间复杂度为O(log2 n)

方案2：分成三堆，如果比较两堆重量一样，则第三堆有假币；如果比较的两堆有一堆教轻，则该堆有假币。重复这个过程，直至找到最轻的硬币，时间复杂度为O(log3 n)

现在让我们把问题复杂化，如果有8枚硬币(a b c d e f g h)，假币重量教轻还是较重，如何处理？

解决这个问题需要使用判定树，具体细节留给大家自己思考。

假币问题乐扣上也没有找到相应的题目，毕竟有值但是又不让用的题比较难出，大家也比较难接受，不过在实际生活中，这个还是很有用的。

总结

减治法和分治法是相似的，只不过减治法每次执行规模会减半。本篇里需要重点关注的有

查找问题：折半查找

排序问题：堆排序、选择问题

其中折半查找大家可能都觉得很容易，其实只是思想理解起来容易，真正编码的时候，涉及到很多边界条件，我用折半查找面试过很多人，能写的完美的比较少。

堆排序是必然要掌握的，关于堆的相关习题太多，大家一定要自己做一番。

最后

大家如果喜欢我的文章，可以关注我的公众号（程序员麻辣烫）

往期文章回顾：

算法

1. 算法学习计划
2. 蛮力法
3. 分治法

技术

1. 浅谈微服务
2. TCP性能优化
3. 限流实现1
4. Redis实现分布式锁
5. Golang源码BUG追查
6. 事务原子性、一致性、持久性的实现原理
7. CDN请求过程详解
8. 记博客服务被压垮的历程
9. 常用缓存技巧
10. 如何高效对接第三方支付
11. Gin框架简洁版
12. InnoDB锁与事务简析

读书笔记

1. 敏捷革命
2. 如何锻炼自己的记忆力
3. 简单的逻辑学-读后感
4. 热风-读后感
5. 论语-读后感

思考

1. 对项目管理的一些看法
2. 对产品经理的一些思考
3. 关于程序员职业发展的思考
4. 关于代码review的思考
5. Markdown编辑器推荐-typora