How to find the Rotation Count in Rotated Sorted array in Python

In this article we shall discuss how to find the rotation count in a rotated sorted array in Python, you can use a binary search. The rotation count represents the index of the minimum element in the array, which indicates the number of times the array has been rotated. A rotated sorted array is an array that has been rotated at some pivot point. Here’s a Python code to find the rotation count in a rotated sorted array in two different approaches:

Approach 1 (using Linear search):

The number of rotations is equal to the index of the minimum element. A simple linear solution is to find the minimum element and return its index.

code:

def countRotations(arr, n):
    min = arr[0]
    min_index = 0
    for i in range(0, n):
        if (min > arr[i]):
            min = arr[i]
            min_index = i
    return min_index;

arr = [12, 18, 2, 4, 7, 14]
n = len(arr)
print(countRotations(arr, n))

output:

2

Approach 2(using Binary search):

A better approach would be to perform binary searching in place of linear search to find the position of the smallest element in the rotated sorted array. Finding the rotation count involves determining how many times the array has been rotated. This function utilizes a binary search approach to find the rotation count of the rotated sorted array efficiently.

Here’s the code for it:

def find_rotation_count(arr):
  low = 0
  high = len(arr) - 1
  n = len(arr)
  while low <= high:
    if arr[low] <= arr[high]:
       return low
    mid = (low + high) // 2
    next_mid = (mid + 1) % n
    prev_mid = (mid + n - 1) % n
    if arr[mid] <= arr[next_mid] and arr[mid] <= arr[prev_mid]:
       return mid
    elif arr[mid] <= arr[high]:
       high = mid - 1
    elif arr[mid] >= arr[low]:
       low = mid + 1

arr = [5,6,7,8,9,10,1,2,3]
print("Rotation count:",find_rotation_count(arr))

output: 6