To find out how many times a sorted array has been rotated, we can look for the position of the smallest element in the array. This works because, in a rotated sorted array, the smallest element is the point of rotation — and its index equals the rotation count.
Case 1: Array is not rotated at all
In this case, the array remains fully sorted in increasing order. So, the smallest element is at index 0. That means the rotation count is 0
.
Case 2: Array has been rotated
If the array has been rotated, the smallest element will appear somewhere after the beginning. The number of steps we had to rotate to get to this state is the index where the smallest element now resides.
For example, in [15, 18, 2, 3, 6, 12]
, the smallest element is 2
at index 2
, meaning the array was rotated 2
times.
Case 3: Empty array
If the array has no elements, there's no rotation to count, and we return -1
to indicate this is not a valid input for rotation logic.
Case 4: Single element
In an array like [2]
, there’s only one element, which is already the smallest and largest at the same time. So, we return 0
as no rotation is needed or detectable.
By using binary search, we can efficiently find the index of the smallest element, which directly tells us the rotation count — all in O(log n)
time, making it much faster than checking every element one by one.