检查向量是否使用除法和impera算法排序

Question

我正在尝试使用分治算法来检查向量是否有序，这是我到目前为止编写的代码：

#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;
}

它在某些情况下似乎不起作用，并且在调试时，我不断添加特定的基本情况以使其可用于一个输入，但这并不能使其适用于另一种输入，直到我意识到我有一个算法错误。我基本上是这样想的：将向量划分为子向量，如果所有子向量都被排序，则整个向量都被排序]。但是，这种方法很快就失效了。如果输入长度不是2的幂，则它将最终将其分解为某些长度为1的子矢量，这些子矢量将始终被排序。例如，如果输入为2 2 3 2 2，该怎么办？子向量是{2，2}，{3}和{2，2}，它们都是有序的，但整个向量不是。

所以我应该怎么看待这个问题？我试图通过添加return v[left-1] <= v[left];行使其长度为1的子矢量工作，但它仍然崩溃。

Answer 1

您为什么还要使用这种“困难”算法？为了检查向量是否归零，每个成员（v[i]）都不能大于下一个成员（v[i+1]）。

例如，“分而治之”算法更有用，它可以在已经排序的向量中查找内容，但是要检查向量是否有序，则简单的线性算法会更好（由于可读性高） 。