Find the Rotation Count in Rotated Sorted array

Problem : Find the count k by which array has been rotated 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

We have to find K?

Solution :

This can be solved in 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 explained in our previous post - Find the minimum element in rotated sorted array.

0 Thoughts on “Find the Rotation Count in Rotated Sorted array

  1. as the array is sorted we can also check the occurance of the first element also .Number of times the first element is encountered till the array is completed is the rotation count

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation