分而治之算法。没有给出正确的输出

Question

我尝试使用“分而治之”算法打印数组的左右部分，但它没有按要求提供输出。 代码如下：

#include <iostream>

using namespace std;

void merge(int *arr, int l, int mid, int r) {
    cout << "Left Part: ";
    for (int i = 0; i < mid + 1; i++) {
        cout << arr[i] << " ";
    }
    // cout << "\n";

    //print right part
    cout << "Right Part: ";
    for (int i = mid + 1; i < r + 1; i++) {
        cout << arr[i] << " ";
    }
    // cout << "\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

不打印打印全阵列

Answer 1

mid

索引的方式不正确：而不是

mid = (l + (r - l)) / 2;

你应该写：mid = l + (r - l) / 2;

另请注意以下备注：

第一个打印循环应从

i = l
• 开始，而不是

  i = 0

  。您应该打印换行符以产生可读的输出。
在您的实现中，

r

是右侧部分最后一个元素的索引，

mid

是左侧部分最后一个元素的索引。这有点令人困惑。在 C 和 C++ 中，惯用的做法是选择

mid

作为右侧部分第一项的索引，并选择

r

作为右侧部分最后一个元素之后的索引。这允许第一次调用使用数组的长度，并避免混乱和容易出错的 +1/-1 调整。这是修改后的版本：

#include <iostream>

using namespace std;

void merge(int *arr, int start, int mid, int end) {
    cout << "Left Part:";
    for (int i = start; i < mid; i++) {
        cout << " " << arr[i];
    }
    cout << "\n";

    //print right part
    cout << "Right Part:";
    for (int i = mid; i < end; i++) {
        cout << " " << arr[i];
    }
    cout << "\n";
}

void divide(int *arr, int start, int end) {
    if (end - start > 1) {
        int mid = start + (end - start) / 2;
        divide(arr, start, mid);
        divide(arr, mid, end);
        merge(arr, start, mid, end);
    }
}

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