Improvement in time complexity of rotatedDistance problem(rotated sorted array)

[Akhilj786]

I came across 2 problem in your approach:

1. If you are doing it O(n) then you could do a simple scan and just minimum value and then return its index. This could have avoided your complex code.
2. Time complexity is O(log n): http://stackoverflow.com/questions/2796413/binary-search-to-find-the-rotation-point-in-a-rotated-sorted-list

[gbrand-salesforce]

Also, this is more of a C code than C++.

The proper C++ solution would consist of a function with 2 lines:

template<typename ForewardIterator>
int get_rotation_dist(ForewardIterator first, ForewardIterator last)
{
    ForewardIterator itr = std::min_element(first, last);
    return std::min(std::distance(first, itr), std::distance(itr, last));
}

While this could be more efficient in runtime as per @Akhilj786 comment, it's much more readable and generic this way (works on all containers) and works the case of duplicate values in the rotated container (as opposed to the O(log n)).