Saturday, August 24, 2013

Find the rotation count in rotated sorted array

Question : Find the minimum element in the rotated sorted array.
So for example we have sorted array as  -
2,3,6,12, 15, 18.
Now suppose the array is rotated k times ( we don't know k), such that array becomes
15, 18,2,3,6,12


Solution
This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array.
So, we need to find the point of inflection where we find a point such that a[i]>a[i+1].

So, finding the minimum element in the rotated sorted array has been implemented here - Find the minimum element in rotated sorted array. Thanks.

0 comments:

Post a Comment