分而治之

什么是分而治之？

在我们前面有学习过一系列数据结构、以及相关的一些算法，包含排序、搜索算法。而本次学习的分而治之它不是数据结构，也不是一种算法，而是算法设计中的一种方法，可以理解为是一种思想。我们可以利用这种思想去设计很多种算法。

分而治之是将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。主要分成三个部分，分别是 "分"、"递归解决"、"合"。

基础案例

场景一

归并排序

分：把数组从中间一分为二
解：递归地对两个子数组进行归并排序
合：合并有序子数组

首先它会把一个大的数组拆分成两个小的数组，再分别对每个小数组又进行拆分成两个小数组，以此类推，最后把单个元素的小数组全部进行合并并排序，最后组成一个大数组从而解决了问题。

归并排序是一个典型的分而治之思想的应用。

场景二

快速排序

分：选基准，按基准把数组分成两个子数组
解：递归地对两个子数组进行快速排序
合：对两个子数组进行合并

步骤如同归并排序类似。

场景三

二分搜索同样具备 "分"、"解"、"合" 的特性。