分治算法

分治将难问题拆成若干规模更小、相互独立的同类子问题，递归解决后再合并。标准三步是：分解、解决、合并。二分查找、快速排序、归并排序和快速幂都是典型应用。

快速幂：按指数折半

利用 a2k=(ak)² 与 a2k+1=a·(ak)²，将线性指数降为对数层数；取模时每步取模避免大数。

long long qpow(long long a, long long b, long long mod) {
    long long ans = 1 % mod;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

时间 O(log b)，额外空间 O(1)。

排序中的分治

归并排序先递归排序左右半区，再用双指针合并，满足 T(n)=2T(n/2)+O(n)=O(n log n)，需 O(n) 临时空间且稳定。快速排序围绕基准划分，左右递归；平均 O(n log n)，最坏 O(n²)，应随机化或合理选择基准。

适用条件

子问题应与原问题同型、规模明显缩小，且合并成本可控。二分本质上也是在具有单调性的搜索空间中每次排除一半。