分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
例1、 比赛安排(noip1996)
设有2^n(n<=6)个球队进行单循环比赛,计划在2^n-1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2^n-1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:
队 1 2 3 4
比赛 1-2 3-4 第一天
1-3 2-4 第二天
1-4 2-3 第三天
算法分析：此题很难直接给出结果，我们先将问题进行分解，设m=2^n，将规模减半，如果n=3(即m=8),8个球队的比赛，减半后变成4个球队的比赛（m=4），4个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛(m=2)，两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可：
1
2
2
1
分析两个球队的比赛的情况不难发现，这是一个对称的方阵，我们把这个方阵分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得到，而右上与左下部分、左上与右下部分别相等。因此我们也可以把这个方阵看作是由M=1的方阵所成生的，同理可得M=4的方阵：
1
2
3
4

2
1
4
3

3
4
1
2

4
3
2
1

同理可由M=4方阵生成M=8的方阵：

1
2
3
4
5
6
7
8

2
1
4
3
6
5
8
7

3
4
1
2
7
8
5
6

4
3
2
1
8
7
6
5

5
6
7
8
1
2
3
4

6
5
8
7
2
1
4
3

7
8
5
6
3
4
1
2

8
7
6
5
4
3
2
1

这样就构成了整个比赛的安排表。
在算法设计中，用数组a记录2^n个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，……直到生成出整个循环比赛表为止。变量h表示当前方阵的大小,也就是要生成的下一个方阵的一半。

源程序：

var
  i,j,h,m,n:integer;
  a:array[1..32,1..32]of integer;
begin
  readln(n);
  m:=1;a[1,1]:=1;h:=1;
for i:=1 to n do m:=m*2;
  repeat
    for i:=1 to h do
      for j:=1 to h do begin
        a[i,j+h]:=a[i,j]+h;{构造右上角方阵}
        a[i+h,j]:=a[i,j+h];{构造左下角方阵}
        a[i+h,j+h]:=a[i,j];{构造右下角方阵}
      end;
    h:=h*2;
  until h=m;
  for i:=1 to m do
  begin
    for j:=1 to m do write(a[i,j]:4);
    writeln;
  end;
end.

在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，由于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比较，时间复杂度由O（N）降到O（log2N），在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的，如下面的例子。
例2 一元三次方程求解（noip2001tg）
题目大意：给出一个一元三次方程f(x)=ax3+bx2+cx+d=0 ,求它的三个根。所有的根都在区间[-100，100]中，并保证方程有三个实根，且它们之间的差不小于1。
算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。
由题意知（i,i+1）中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100≤x≤100),设定搜索区间[x1，x2]，其中x1=x，x2=x+1。若：
⑴f(x1)=0，则确定x1为f(x)的根；
⑵f(x1)*f(x2)0，则确定根x不在区间[x1，x2]内，设定[x2，x2+1]为下一个搜索区间；
若确定根x在区间[x1，x2]内，采用二分法，将区间[x1，x2]分成左右两个子区间：左子区间[x1，x]和右子区间[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，则确定根在左区间[x1，x]内，将x设为该区间的右界值（x2=x），继续对左区间进行对分；否则确定根在右区间[x，x2]内，将x设为该区间的左界值（x1=x），继续对右区间进行对分；
上述对分过程一直进行到区间的间距满足精度要求为止（即x2-x1<0.005）。此时确定x1为f(x)的根。

源程序：

{$N+}
var
  x:integer;
  a,b,c,d,x1,x2,xx:extended;
function f(x:extended):extended;
begin
  f:=((a*x+b)*x+c)*x+d;
end;
begin
  read(a,b,c,d);
  for x:=-100 to 100 do
  begin
    x1:=x;x2:=x+1;
    if f(x1)=0 then write(x1:0:2,’ ‘)
    else if f(x1)*f(x2)<0 then
    begin
      while x2-x1>=0.005 do
      begin
        xx:=(x1+x2)/2;
        if f(x1)*f(xx)<=0 then x2:=xx
        else x1:=xx;
      end;{while}
      write(x1:0:2,’ ‘);
    end; {then}
  end;{for}
end.