Check if an array is sorted and rotated using Binary Search | Function to return the index of the pivot ; Base cases ; Check if element at ( mid - 1 ) is pivot Consider the cases like { 4 , 5 , 1 , 2 , 3 } ; Decide whether we need to go to the left half or the right half ; Function to check if a given array is sorted rotated or not ; To check if the elements to the left of the pivot are in descending or not ; To check if the elements to the right of the pivot are in ascending or not ; If any of the above if or else is true Then the array is sorted rotated ; Else the array is not sorted rotated ; Driver code
def findPivot ( arr , low , high ) : NEW_LINE INDENT if ( high < low ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT if ( high == low ) : NEW_LINE INDENT return low ; NEW_LINE DEDENT mid = ( low + high ) // 2 ; NEW_LINE if ( mid < high and arr [ mid + 1 ] < arr [ mid ] ) : NEW_LINE INDENT return mid ; NEW_LINE DEDENT if ( mid > low and arr [ mid ] < arr [ mid - 1 ] ) : NEW_LINE INDENT return mid - 1 ; NEW_LINE DEDENT if ( arr [ low ] > arr [ mid ] ) : NEW_LINE INDENT return findPivot ( arr , low , mid - 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT return findPivot ( arr , mid + 1 , high ) ; NEW_LINE DEDENT DEDENT def isRotated ( arr , n ) : NEW_LINE INDENT l = 0 ; NEW_LINE r = n - 1 ; NEW_LINE pivot = - 1 ; NEW_LINE if ( arr [ l ] > arr [ r ] ) : NEW_LINE INDENT pivot = findPivot ( arr , l , r ) ; NEW_LINE temp = pivot NEW_LINE if ( l < pivot ) : NEW_LINE INDENT while ( pivot > l ) : NEW_LINE INDENT if ( arr [ pivot ] < arr [ pivot - 1 ] ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT pivot -= 1 ; NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT pivot = temp NEW_LINE pivot += 1 ; NEW_LINE while ( pivot < r ) : NEW_LINE INDENT if ( arr [ pivot ] > arr [ pivot + 1 ] ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT pivot + + 1 ; NEW_LINE DEDENT DEDENT return True ; NEW_LINE DEDENT else : NEW_LINE INDENT return False ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 4 , 5 , 1 , 2 ] ; NEW_LINE if ( isRotated ( arr , 5 ) ) : NEW_LINE INDENT print ( " True " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " False " ) ; NEW_LINE DEDENT DEDENT