分治法（Divide and Conquer）的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的几个相似问题，以便各个击破，分而治之。

说明：

分治策略的应用很广，具体表现形式各异，比如：折半查找、合并排序、快速排序、二叉树遍历（先遍历左子树再遍历右子树）、二叉排序树的查找等算法。

一、分治算法框架

1、算法设计思想

分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

由算法思路可知，分治法求解很自然地可以用一个递归过程来表示，可以这样说分治方法就是一种找大规模问题与小规模问题关系的方法，是递归设计方法的一种具体策略。分治法的基本步骤在每一层递归上都有3个步骤。

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
• 解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；
• 合并：将已求解的各个子问题的解，逐步合并为原问题的解。

2、适合用分治法策略的问题

当求解一个输入规模为n且取值又相当大的问题时，用蛮力策略效率一般得不到保证。若问题能满足以下几个条件，就能用分治法来提高解决问题的效率。

• 能将这n个数据分解成k个不同子集合，且得到k个子集合是可以独立求解的子问题，其中1 < k <= n；
• 分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制；
• 在求出这些子问题的解之后，就可以推解出原问题的解。

3、算法框架

分治法的一般的算法设计模式如下：

Divide-and-Conquer(n)                      // n为问题规模
{
	if(n <= n0)                            // n0为可解子问题的规模
	{
		解子问题;
			return (子问题的解);
	}
	for(i = 1; i <= k; i++)                // 分解为较小的k个子问题P1, P2, ..., Pk
	{
		分解原问题为更小的子问题Pi;
			yi = Divide-and-Conquer(|Pi|); // 递归解决Pi，|Pi|为Pi的规模
	}
	T = MERGE(y1, y2, ..., yk);            // 合并子问题
	return T;
}

二、典型的二分法

在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，称为二分法。二分法是分治法较常用的分解策略，比如折半查找、归并排序算法都是采用此策略实现的。

1、金块问题

老板有一袋金块（共n块，n是2的幂（n >= 2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

解析：

问题可以简化为，在含n个元素的集合中寻找最大值和最小值。

(1)将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大（小）值。

(2)递归分解直到每组元素的个数<= 2，可简单地找到最大（小）值。

(3)回溯时合并子问题的解，在两个子问题的解中大者取大，小者取小，即合并为当前问题的解。

算法实现：

#include<stdio.h>

float a[10] = {21, 56, 43, 12, 3, 99, 56, 23, 2, 12};
void maxmin(int i, int j, float& fmax, float& fmin)
{ // i表示区间低位下标；j表示区间高位下标
  // fmax表示数组a[n]最大值；fmin表示数组a[n]最小值
	int mid;
  // lmax表示左半区间最大值；lmin表示左半区间最小值
  // rmax表示右半区间最大值；rmin表示右半区间最小值
	float lmax, lmin, rmax, rmin;

	if(i == j)        // 表示数组a[n]含有一个元素
	{
		fmax = a[i];
		fmin = a[i];
	}
	else if(i == j-1) // 表示数组a[n]含有两个元素
		if(a[i] < a[j])
		{
			fmax = a[j];
			fmin = a[i];
		}
		else
		{
			fmax = a[i];
			fmin = a[j];
		}
	else              // 表示数组a[n]含有多于两个元素
	{
		mid = (i+j) / 2;              // 区间中点
		maxmin(i, mid, lmax, lmin);   // 左半区间
		maxmin(mid+1, j, rmax, rmin); // 右半区间
		if(lmax > rmax)
			fmax = lmax;
		else
			fmax = rmax;
		if(lmin > rmin)
			fmin = rmin;
		else
			fmin = lmin;
	}
}

void main() 
{
	float a, b;
	maxmin(0, 9, a, b);
	printf("%f\n", a);
	printf("%f\n", b);
}

三、二分法不相似情况

四、二分法不独立情况

五、非等分分治

选择问题就是“从一组数中选择第k小的数据”，这个问题不能用典型的二分法分解成完全独立、相似且“互相相等”的两个子问题。因为二等分数据后，可以选出第一组的第k小的数据和第二组的第k小的数据，但不能保证这两个数据之一就是原问题的解，即问题经二等分后的子问题不独立。

1、求一组数的第二小的数据

解析：

在用二等分法分解的两个子集中，无论只选取第二小数据或只选取最小的数据，合并处理后都有可能得不到原问题的正确解。但若在两个子集中都选取最小的两个值，那么，原问题中第二小的数据则一定在这4个数之中。显然，将问题转化为“求一组数中较小的两个数”后，二等分法分解后就可将原问题“分解为与原问题独立且相似的两个子问题”了。这样，回溯合并的过程就是从两个子问题选出的共4个数中，选取出较小的两个数；直到回溯结束，就得到一组数中较小的两个数。从而也就得到了原问题的解，求出了一组数中第二小的数据。

#include<stdio.h>

float a[100] = {21, 56, 43, 12, 3, 99, 56, 23, 2, 12};
void two(int i, int j, float& fmin2, float& fmin1)
{ // i表示区间低位下标；j表示区间高位下标
  // fmin2表示数组a[n]第二小数；fmin1表示数组a[n]第一小数
	float lmin2, lmin1, rmin2, rmin1;
  // lmin2表示左半区间第二小数；lmin1表示左半区间第一小数
  // rmin2表示右半区间第二小数；rmin1表示右半区间第一小数
	int mid;
	if(i == j)                        // 表示数组a[n]含有一个元素
		fmin2 = fmin1 = a[i];
	else if(i == j-1)                 // 表示数组a[n]含有两个元素
	{
		if(a[i] < a[j])
		{
			fmin2 = a[j];
			fmin1 = a[i];
		}
		else 
		{
			fmin2 = a[i];
			fmin1 = a[j];
		}
	}
	else                              // 表示数组a[n]含有多于两个元素
	{
		mid = (i+j) / 2;              // 区间中点
		two(i, mid, lmin2, lmin1);    // 左半区间
		two(mid+1, j, rmin2, rmin1);  // 右半区间
		if(lmin1 < rmin1)
			if(lmin2 < rmin1)
			{
				fmin1 = lmin1;
				fmin2 = lmin2;
			}
			else
			{
				fmin1 = lmin1;
				fmin2 = rmin1;
			}
		else
			if(rmin2 < lmin1)
			{
				fmin1 = rmin1;
				fmin2 = rmin2;
			}
			else
			{
				fmin1 = rmin1;
				fmin2 = lmin1;
			}
	}
}

float second(int n)
{
	float min2, min1;
	two(0, n-1, min2, min1);
	return min2;
}

void main() 
{
	float min2;
	min2 = second(10);
	printf("%f\n", min2);
}