Check if a vector is ordered using divide et impera algorithm

Question

I am trying to check if a vector is ordered using the divide and conquer algorithm, here's the code I wrote so far:

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

It can't seem to work for certain cases and while debugging I kept adding specific base cases to make it work for one input but that would not make it work for another input, and I kept doing that until I realized I had an algorithmic error. I basically thought of it like this: Divide the vector up into sub-vectors and if all sub-vectors are ordered then the whole vector is ordered. However this approach very quickly breaks down. If the input length is not a power of 2 then it will eventually break it down into certain sub-vectors of length 1 which will always be ordered. For example what if the input is 2 2 3 2 2? The sub-vectors are {2, 2}, {3} and {2, 2} and all of them are ordered but the whole vector is not.

So how should I think this problem instead? I tried to make it work for sub-vectors of length 1 by adding that return v[left-1] <= v[left]; line but it still breaks down.

Answer 1

Beginning with recursion:

range is ordered if both subranges is ordered and if last item of "low" range is lower than first item of "high" range:

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

Remains the stop condition: when range is empty (cannot happen from argument) or has only one element. Those are ordered ranges.

So we got:

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