减治法(reduce and conquer method)同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。所以，严格地说，减治法应该是一种退化了的分治法。应用减治法技术设计的算法通常具有很高的效率，一般来说其时间复杂性是$O(log_2n)$。

减治法的设计思想

  减治法在将原问题分解为若干个子问题后，利用了规模为n的原问题的解与较小规模(通常是n/2)的子问题的解之间的关系，这种关系通常表现为:
(1)原问题的解只存在于其中一个较小规模的子问题中；
(2)原问题的解与其中一个较小规模的解之间存在某种对应关系。

查找问题中的减治法

折半查找

  折半查找法适用于在有序列表中查找特定的元素，把带查找的数据值与查找范围的中间元素进行比较，会有三种情况出现：
(1)待查找数据值与中间元素值正好相等，则放回中间元素值的索引。
(2)待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行（1）,知道找到相等的值。
(3)待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行（1），直到找到相等的值。

int BiSearch(int data[], int x, int beg, int last)
{
    int mid;
    if(beg > last)
    {
        return -1;
    }

    while(beg <= last)
    {
        mid = (beg + last) / 2;
        if(x == data[mid])
        {
            return mid;
        }
        else if(data[mid] < x)
        {
            beg = mid + 1;
        }
        else
        {
            last = mid - 1;
        }
    }

    return -1;
}

二叉查找树

概念 二叉查找树(binary search trees),又称二叉排序树，是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上的所有结点的值均小于根结点的值；
（2）若它的右子树不空，则右子树上所有节点的值均大于根结点的值；
（3）它的左右子树也都是二叉排序树。
  在二叉排序树root种查找给定值k的过程是：
（1）若root是空树，则查找失败
（2）若k=根结点的值，则查找成功
（3）否则，若k < 根节点的值，则在root的左子树上查找
（4）否则，在root的右子树上查找
  上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。

struct BiNode
{
    int data;
    BiNode *lchild;
    BiNode *rchild;
}
BiNode *SearchBST(BiNode *root int k)
{
    if(root == NULL)
    {
        return NULL;
    }
    else if(root->data == k)
    {
        return root;
    }
    else if(k < root->data)
    {
        return SearchBST(root->lchild, k);
    }
    else
    {
        return SeachBST(root->rchild, k);
    }
}

排序问题中的减治法

堆排序 堆是具有下列性质的完全二叉树：每个节点的值都小于或等于其左右孩子节点的值（小根堆）；或者每个节点的值都大于或等于其左右孩子节点的值（大根堆）。
  堆排序就是利用堆进行排序的方法，它的基本思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复，便可得到一个有序序列了。
  

#define MAXSIZE 10 /*排序数组个数最大值*/
typedef struct
{
    int r[MAXSIZE+1]; /*r[0]作为哨兵或临时变量*/
    int length;      /*记录顺序表的长度*/
}SqList;
void swap(SqList *L, int i, int j)
{
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->[j] = temp;
}
/*
已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义
本函数调整L->r[s]的关键字，使L->r[s..m]成为一个大顶堆。
*/
void HeapAdjust(SqList *L, int s, int m)
{
    int temp;
    int j;
    temp = L->r[s];

    /* 沿关键字较大的孩子节点向下筛选*/
    for(j = 2*s; j<=m; j*=2)
    {
        if(jr[j] < L->r[j+1])
        {
            ++j;    /* j 作为关键字中较大记录的下标*/
        }

        if(temp >= L->r[j])
        {
            break;
        }
        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = temp;
}
void HeapSort(SqList *L)
{
    int i;
    for(i = L->length/2; i>0; i--)
    {
        HeapAdjust(L, i, L->length);
    }

    for(i = L->length; i>1; i--)
    {
        swap(L,1,i);
        HeapAdjust(L, 1, i-1);
    }
}

  上文中使用的是筛选法进行堆的调整，《算法设计与分析》中介绍了插入法调整堆，该方法具有更简洁的思路。