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 both of the above if is true Then the array is sorted rotated ; Else the array is not sorted rotated ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findPivot ( int arr [ ] , int low , int high ) { if ( high < low ) return -1 ; if ( high == low ) return low ; int mid = ( low + high ) / 2 ; if ( mid < high && arr [ mid + 1 ] < arr [ mid ] ) { return mid ; } if ( mid > low && arr [ mid ] < arr [ mid - 1 ] ) { return mid - 1 ; } if ( arr [ low ] > arr [ mid ] ) { return findPivot ( arr , low , mid - 1 ) ; } else { return findPivot ( arr , mid + 1 , high ) ; } } bool isRotated ( int arr [ ] , int n ) { int l = 0 ; int r = n - 1 ; int pivot = -1 ; if ( arr [ l ] > arr [ r ] ) { pivot = findPivot ( arr , l , r ) ; int temp = pivot ; if ( l < pivot ) { while ( pivot > l ) { if ( arr [ pivot ] < arr [ pivot - 1 ] ) { return false ; } pivot -- ; } } pivot = temp ; if ( pivot < r ) { pivot ++ ; while ( pivot < r ) { if ( arr [ pivot ] > arr [ pivot + 1 ] ) { return false ; } pivot ++ ; } } return true ; } else { return false ; } } int main ( ) { int arr [ ] = { 4 , 5 , 1 , 3 , 2 } ; if ( isRotated ( arr , 5 ) ) cout << " true " ; else cout << " false " ; return 0 ; }