减治法

减治法（Decrease and Conquer）每一步把问题规模缩小，再对更小的问题求解。与分治不同，它通常不是拆成多个彼此独立的子问题再合并，而是「变小一点，继续做」。

本文解决什么问题

• 减治的三种缩小方式
• 为什么二分查找是减治而不是典型分治
• 如何从「每次排除多少」判断复杂度

常见缩小方式

类型	含义	例子
减常量	每次规模减固定值（常为 1）	插入排序外层；递归求阶乘
减常因子	每次按比例缩小（常为减半）	二分查找
减可变规模	根据数据决定缩小多少	某些选择问题、欧几里得算法

典型例子：二分查找

有序数组上每次与中间元素比较，只进入一侧，规模近似减半：

int binary_search(const int *a, int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) {
            return mid;
        }
        if (a[mid] < target) {
            left = mid + 1;     /* 规模缩小到右半 */
        } else {
            right = mid - 1;    /* 规模缩小到左半 */
        }
    }
    return -1;
}

• 时间：$O(\log n)$
• 空间：迭代版 $O(1)$；递归版 $O(\log n)$ 栈深度

详见 二分查找。

例子：欧几里得算法求最大公约数

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;          /* 规模按余数变小 */
    }
    return a;
}

问题规模用数值大小衡量，每步用余数替换，属于「减可变规模」的减治思想。

和分治的边界

问题	更像哪种	原因
二分查找	减治	每次只递归/进入一侧
归并排序	分治	左右都要处理，再合并
快速排序	分治	分区后左右通常都要递归
阶乘递归	减治（减一）	规模 $n \rightarrow n-1$，一个子问题

备注

快速排序的「分区」本身很像在缩小问题，但完整算法要对两侧都排序，因此整体归入分治更合适。

复杂度直觉

• 每次减 1，工作 $O(1)$ → 常 $O(n)$
• 每次减半，工作 $O(1)$ → 常 $O(\log n)$
• 每次减半，但每层还扫一遍 $O(n)$ → 要想清楚是「一层」还是「整棵递归树」

写减治时的检查清单

1. 缩小后是否一定更接近终止条件？
2. 被排除的那部分是否确定不可能含答案？（二分依赖有序）
3. 用循环还是递归？深度是否可控？

小结

看到「每次排除一大块可能性」或「规模稳定变小」，先想想是不是减治。二分查找是最好的入门锚点。

下一篇：贪心法。