Find the Rotation Count in Rotated Sorted array | Returns count of rotations for an array which is first sorted in ascending order , then rotated ; This condition is needed to handle the case when array is not rotated at all ; If there is only one element left ; Find mid ; Check if element ( mid + 1 ) is minimum element . Consider the cases like { 3 , 4 , 5 , 1 , 2 } ; Check if mid itself is minimum element ; Decide whether we need to go to left half or right half ; Driver code
def countRotations ( arr , low , high ) : NEW_LINE INDENT if ( high < low ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( high == low ) : NEW_LINE INDENT return low NEW_LINE DEDENT mid = low + ( high - low ) / 2 ; NEW_LINE mid = int ( mid ) NEW_LINE if ( mid < high and arr [ mid + 1 ] < arr [ mid ] ) : NEW_LINE INDENT return ( mid + 1 ) NEW_LINE DEDENT if ( mid > low and arr [ mid ] < arr [ mid - 1 ] ) : NEW_LINE INDENT return mid NEW_LINE DEDENT if ( arr [ high ] > arr [ mid ] ) : NEW_LINE INDENT return countRotations ( arr , low , mid - 1 ) ; NEW_LINE DEDENT return countRotations ( arr , mid + 1 , high ) NEW_LINE DEDENT arr = [ 15 , 18 , 2 , 3 , 6 , 12 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countRotations ( arr , 0 , n - 1 ) ) NEW_LINE