c++ - 使用divide et impera 算法检查 vector 是否有序

Question

我正在尝试使用分而治之算法检查 vector 是否有序，这是我到目前为止编写的代码:

#include <iostream>
#include <vector>

using namespace std;

bool isOrdered(std::vector <int> v, int left, int right)
{
int mid = (left + right)/2;

if (left == right){
    if (left == 0)
        return true;
    else
        return v[left-1] <= v[left];
}
else if (left + 1 == right)
{
    if (v[left] <= v[right])
        return true;
    else
        return false;
}
else if (left > right)
{
    if (v[left] > v[right])
        return true;
    else
        return false;
}
else
{
    return isOrdered(v, left, mid) && isOrdered(v, mid+1, right);
}
}

int main()
{
std::vector <int> v = {2, 2, 3, 2, 2};
cout << isOrdered(v, 0, v.size() - 1);
return 0;
}

它似乎不适用于某些情况，在调试时，我不断添加特定的基本情况以使其适用于一个输入，但这不会使其适用于另一输入，我一直这样做，直到我意识到我有算法错误。我基本上是这样想的:将 vector 划分为子 vector ，如果所有子 vector 都已排序，则整个 vector 也已排序。然而这种方法很快就失效了。如果输入长度不是 2 的幂，那么它最终会将其分解为某些长度为 1 的子 vector ，并且这些子 vector 始终是有序的。例如，如果输入是2 2 3 2 2怎么办？ ？子 vector 是 {2, 2}、{3} 和 {2, 2}，它们都是有序的，但整个 vector 不是有序的。

那么我应该如何看待这个问题呢？我试图通过添加 return v[left-1] <= v[left]; 来使其适用于长度为 1 的子 vector 。线，但还是坏了。

Answer 1

从递归开始:

如果两个子范围都已排序并且如果“低”范围的最后一项低于“高”范围的第一项，则对范围进行排序:

return isOrdered(v, left, mid - 1) && isOrdered(v, mid, right) && v[mid - 1] <= v[mid];

保持停止条件:当范围为空(不能从参数中发生)或只有一个元素时。 这些是有序范围。

所以我们得到:

bool isOrdered(const std::vector<int>& v, std::size_t left, std::size_t right)
{
    if (left == right) { // Only one element
        return true;
    } else {
        const auto mid = (left + right + 1) / 2;
        return v[mid - 1] <= v[mid]
            && isOrdered(v, left, mid - 1)
            && isOrdered(v, mid, right);
    }
}