分治（Divide and conquer）算法无法输出完整数组求助

问题根源 #

你的代码存在两个核心错误，导致无法完整打印所有分治阶段的数组部分：

• 中点计算逻辑错误：原代码中mid = (l + (r - l)) / 2等价于mid = r / 2，当分治到非起始区间（比如l=2, r=3）时，mid会小于l，直接破坏分治递归逻辑，导致后续merge操作无法触发。
• 打印区间错误：merge函数中左部分循环从i=0开始，会打印数组前mid+1个元素，而非当前分治的目标区间[l, mid]，无法正确展示当前分治段的左半部分。

修正后的代码 #

#include <iostream>

using namespace std;

void merge(int *arr, int l, int mid, int r) {
    cout << "Left Part: ";
    // 打印当前分治的左区间[l, mid]
    for (int i = l; i <= mid; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";

    cout << "Right Part: ";
    // 打印当前分治的右区间[mid+1, r]
    for (int i = mid + 1; i <= r; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n-----------------\n";
}

void divide(int *arr, int l, int r) {
    int mid;
    if (l < r) {
        // 正确计算中点，避免溢出且符合分治逻辑
        mid = l + (r - l) / 2;

        divide(arr, l, mid);
        divide(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

int main() {
    int arr[] = { 38, 27, 43, 3, 9, 82, 10 };
    divide(arr, 0, 6);
    return 0;
}

修正后输出示例 #

Left Part: 38 
Right Part: 27 
-----------------
Left Part: 43 
Right Part: 3 
-----------------
Left Part: 38 27 
Right Part: 43 3 
-----------------
Left Part: 9 
Right Part: 82 
-----------------
Left Part: 9 82 
Right Part: 10 
-----------------
Left Part: 38 27 43 3 
Right Part: 9 82 10 
-----------------

内容的提问来源于stack exchange，提问作者Amit Kumar