Find the number of rotations in a circularly sorted array.

Here’s how we can approach solving the "Find the number of rotations in a circularly sorted array" problem:

1. Calculate the Length: First, determine the length of the input array.
2. Handle Edge Cases: If the array is empty, return 0, as there are no rotations in an empty array.
3. Check if Array is Already Sorted: If the first element is less than or equal to the last element, return 0 because the array has not been rotated.
4. Initialize Variables: Set up two pointers: start and end, pointing to the first and last elements of the array, respectively.
5. Perform Binary Search: While start is less than end, calculate the midpoint. Use binary search to identify the point of inflection where the rotation occurs:
   • If arr[mid] is greater than arr[mid + 1], the inflection point is found, and the number of rotations is mid + 1.
   • If arr[start] is less than or equal to arr[mid], the inflection point is in the right half, so move start to mid + 1.
   • Otherwise, move end to mid.
6. Return the Result: After the binary search completes, return 0 if no rotation is found.

Here is the function implementation:

Time Complexity: The binary search operates in O(log n) time since we divide the search space in half with each iteration.

Space Complexity: The space complexity is O(1) since the algorithm only uses a constant amount of extra space.