c++ - 如何使用递归并分成两半来找到数组中的最大值？

Question

我的教授希望我们使用递归来查找数组中的最大值，特别是通过分治法。我的意思是他希望我们将阵列分成两半，沿着下半部向下移动，然后穿过上半部。

但是，我在使用代码时遇到了几个问题。首先，我很困惑，因为我不确定如何让阵列停止穿过下半部分？我正在添加条件检查以查看它是否正在经历无限循环，但它有点忽略它。此外，它似乎在一开始就不应该出现的情况下出现在阵列之外。然后，使用他给出的示例代码，使用它似乎在 10 位数组中跳过所有奇数的标志。

我的代码在这里

#include <iostream>

using namespace std;


int maxarray(const int anarray[], int first, int last)
{
    cout << "call" << endl;
    cin.get();
    int mid = first + (last - first) / 2;
    int firstHalf,lastHalf = 0;
    do{
        cout << firstHalf << " - " << mid << endl;
        cin.get();
    firstHalf = maxarray(anarray, first, mid - 1);
    }
    while(mid!= first);

    do{
    lastHalf = maxarray(anarray, mid+1, last);
    }
    while(mid != last);
    if(firstHalf <= lastHalf)
        return lastHalf;
    else if(lastHalf <= firstHalf)
            return firstHalf;
    else
        return -1;


    }

int main()
{
    int arr[10] = {1,2,3,4,5,6,7,8,9,0};


    for(int x=0;x<10;x++){
        cout << arr[x] << endl;}

    cout << maxarray(arr,0, 10);
}

然后使用我得到的输出

1
2
3
4
5
6
7
8
9
0
call

0 - 5

call

16777216 - 2

call

16777216 - 0

它在最后一个条目之后进入无限循环。我不确定我做错了什么，谷歌搜索让我得到简单的答案，但不是他希望我做的那样。我的教科书只给了我伪代码，但也无济于事。从概念上讲，我明白我应该如何工作，但我在应用它时遇到了麻烦。我会向他发送问题，但他只是将我转发到 StackOverflow 和其他网站寻求帮助。

Answer 1

你对这个问题想得太多了。通过分而治之策略递归地找到最大值的过程非常简单:

• 如果因为范围只有一个项目而没有什么可划分的，则返回该项目
• 否则将范围一分为二，在两半上调用最大值，并返回两者中较大的一个

代码如下:

int maxarray(const int a[], int first, int last) {
    // Single-item range
    if (first+1 == last) {
        return a[first];
    }
    // Divide-and-conquer
    int mid = first + (last - first) / 2;
    int leftMax = maxarray(a, first, mid);
    int rightMax = maxarray(a, mid, last);
    return leftMax > rightMax ? leftMax : rightMax;
}

Demo.

请注意，尽管我们划分了范围，但算法仍然是线性的，因为我们在所有情况下都解决了两个子问题。换句话说，我们必须查看范围内的每一项，而不考虑顺序。