Here is my minimal solution about the problem
[m .. p P .. M]
with
[P .. M m .. p]
so the idea is to update the l
left cursor and r
right cursor so that v[l] > v[r]
with a divide and conquer strategy so to have O(LogN)
complexity and ultimately the final condition is l
and r
are contiguous
and the first identifies M
while the second identifies m
hence return the last one
EDIT Following @papagaga suggestion I provide 2 implementations
1. Index based solution
#include <iostream>
#include <vector>
using namespace std;
vector<int> a = {5,6,7,8,9,10,11, 1,2,3,4};
unsigned int solve(const vector<int>& a, unsigned int l=0, unsigned int r=0)
{
if(a.empty()) throw runtime_error("Empty");
if(a.size()==1) return 0;
if(r==0) r=a.size()-1; ///< Overwrite the invalid initialization with the right value, unfortunately it is not possible to do this in function declaration
if(a[l] < a[r]) return l; ///< Sorted in Ascending Order
if(r-l==1) return r;
const auto m = (r+l)/2;
if(a[m] > a[l]) return solve(a, m, r);
return solve(a, l, m);
}
int main() {
// your code goes here
cout << "Min=" << a[solve(a)];
return 0;
}
Comments
- Added the empty array case management using Exception
- An alternative could have been using Maybe Monad (a Boost Optional) to represent non meaningful results
2. Iterators based solution
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
vector<int> a = {5,6,7,8,9,10,11, 1,2,3,4};
vector<int>::iterator solve(const vector<int>::iterator l, const vector<int>::iterator r)
{
if(l==r) return r; ///< Covers the single element array case
if(*l < *r) return l; ///< Sorted in Ascending Order
if(r-l==1) return r;
const auto m = l + distance(l,r)/2;
if(*m > *l) return solve(m, r);
return solve(l, m);
}
int main() {
// your code goes here
cout << "Min=" << *solve(a.begin(), a.end()-1);
return 0;
}
Comments
- Working with iterators allows to represent invalid values so no need for Exception and explicit Maybe Monad as the iterator type is one
- The first check automatically manages the one element case
- The empty array case should be managed before calling this function as it expects both the iterators point to valid elements