分治算法实战解析：从归并排序到循环赛日程安排
分治法的核心思想是"分而治之"，将大问题逐步分解为小问题独立求解，再合并结果。本文通过多个经典实例，展示分治策略在排序、查找和日程安排中的应用。
例1 归并排序详解
归并排序是分治法的典型代表。其过程可概括为：
- 将数组不断二分，直至每组只剩一个元素（天然有序）
- 将相邻的两个有序组逐对合并，合并时按大小排列
以数组 {7, 3, 9, 1, 6, 2} 为例：
- 第一次拆分：left=[7,3,9]，right=[1,6,2]
- 继续拆分，最终每组单元素
- 合并时比较两端，小的先进临时数组
- 若某侧先空，另一侧剩余元素直接复制
实现代码（C++ 精简版）：
#include <iostream>
using namespace std;
const int N = 100000;
int arr[N], tmp[N];
void mergeSort(int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(l, mid);
mergeSort(mid + 1, r);
int i = l, j = mid + 1, pos = 0;
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) tmp[pos++] = arr[i++];
else tmp[pos++] = arr[j++];
}
while (i <= mid) tmp[pos++] = arr[i++];
while (j <= r) tmp[pos++] = arr[j++];
for (int k = 0; k < pos; ++k) arr[l + k] = tmp[k];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> arr[i];
mergeSort(0, n - 1);
for (int i = 0; i < n; ++i) cout << arr[i] << " ";
return 0;
}
例2 折半查找算法
折半查找（二分查找）要求数据已有序。查找过程如下：
- 取中间元素与目标值比较
- 若相等则找到
- 若目标值大于中间值，则在右半部分递归查找
- 若目标值小于中间值，则在左半部分递归查找
例如在有序数组 [1,2,3,4,5,6,7,8,9] 中查找 8，依次比较 5、7、8，三次即找到。
代码实现（递归版本）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100000;
int data[N];
int binSearch(int l, int r, int target) {
if (l > r) return -1;
int mid = (l + r) >> 1;
if (data[mid] == target) return mid + 1;
if (target > data[mid]) return binSearch(mid + 1, r, target);
return binSearch(l, mid - 1, target);
}
int main() {
int n, x;
cin >> n >> x;
for (int i = 0; i < n; ++i) cin >> data[i];
sort(data, data + n);
cout << binSearch(0, n - 1, x);
return 0;
}
扩展：支持重复元素查找
若序列中存在多个相同值，需找出所有匹配位置。可通过调整递归条件实现：当中间值等于目标时，记录位置并继续向左右两侧查找。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100000;
int arr[N];
vector<int> results;
void multiSearch(int l, int r, int target) {
if (l > r) return;
int mid = (l + r) >> 1;
if (arr[mid] == target) results.push_back(mid + 1);
if (l == r) return;
if (target >= arr[mid]) multiSearch(mid + 1, r, target);
if (target <= arr[mid]) multiSearch(l, mid - 1, target);
}
int main() {
int n, x;
cin >> n >> x;
for (int i = 0; i < n; ++i) cin >> arr[i];
sort(arr, arr + n);
multiSearch(0, n - 1, x);
for (int pos : results) cout << pos << " ";
return 0;
}
例3 循环赛日程表生成
设计一个算法，为 N 支球队（N 为 2 的幂）生成赛程表，使得每两支球队恰好相遇一次。采用分治策略，核心思路为：
- 初始化 2 支球队的赛程：队1 vs 队2
- 扩充时，将当前已知的赛程复制到四个象限：左上角不变，右上角和左下角元素加偏移量，右下角与左上角相同
以 8 支球队为例，赛程表为 8×8 矩阵，第 i 行第 j 列代表第 i 天第 j 支球队的对手。
#include <iostream>
#include <cmath>
using namespace std;
const int MAX = 100;
int schedule[MAX][MAX];
void generate(int teams) {
schedule[0][0] = 1; schedule[0][1] = 2;
schedule[1][0] = 2; schedule[1][1] = 1;
for (int k = 1; k <= log2(teams) - 1; ++k) {
int half = pow(2, k);
for (int i = 0; i < half; ++i) {
for (int j = 0; j < half; ++j) {
schedule[i + half][j] = schedule[i][j] + half;
schedule[i][j + half] = schedule[i][j] + half;
schedule[i + half][j + half] = schedule[i][j];
}
}
}
}
int main() {
int n;
cout << "输入队伍数量（2的幂）：";
cin >> n;
generate(n);
cout << "赛程表：\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
cout << schedule[i][j] << "\t";
cout << "\n";
}
return 0;
}
若实际队伍数不是 2 的幂，可先按大于它的最小 2 的幂生成赛程，再删除多余行与列。
实践题：找假硬币
16 枚硬币中有一枚假币（重量 5g），其余真币 6g。用分治法找出假币位置：
- 每次将硬币分成两堆，计算左堆重量
- 若左堆总重为奇数，则假币在左堆（因为 6 是偶数，奇数重量必含 5）
- 否则假币在右堆
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int coins[18];
int findFake(int l, int r) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (coins[mid] % 2) return mid;
int leftSum = 0, rightSum = 0;
for (int i = l; i < mid; ++i) leftSum += coins[i];
for (int i = mid + 1; i <= r; ++i) rightSum += coins[i];
if (leftSum % 2) return findFake(l, mid);
else return findFake(mid + 1, r);
}
int main() {
for (int i = 1; i <= 16; ++i) coins[i] = 6;
srand(time(0));
coins[rand() % 16 + 1] = 5;
cout << "假币位置：" << findFake(1, 16);
return 0;
}
自学探索
1. 查找最大值与次大值
通过分治，将数组分成两半，分别求每半的最大值和次大值，再合并比较得出全局结果。
#include <iostream>
#include <algorithm>
using namespace std;
int data[] = {2, 5, 1, 4, 6, 3};
void findMaxTwo(int l, int r, int &max1, int &max2) {
if (l == r) {
if (data[l] > max1) { max2 = max1; max1 = data[l]; }
else max2 = max(max2, data[l]);
return;
}
int mid = (l + r) >> 1;
findMaxTwo(l, mid, max1, max2);
findMaxTwo(mid + 1, r, max1, max2);
}
int main() {
int a = 0, b = 0;
findMaxTwo(0, 5, a, b);
cout << "最大值：" << a << " 次大值：" << b;
return 0;
}
2. 两个等长有序序列的中位数
最直接的方法是将两个序列合并排序后取中间值，时间复杂度 O(n log n)。若追求更优算法，可采用二分排除法，每次排除一半不可能包含中位数的元素。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100000;
int merged[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < 2 * n; ++i) cin >> merged[i];
sort(merged, merged + 2 * n);
cout << merged[(0 + 2 * n - 1) >> 1];
return 0;
}
