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
< ? php function countRotations ( $ arr , $ low , $ high ) { if ( $ high < $ low ) return 0 ; if ( $ high == $ low ) return $ low ; $ mid = $ low + ( $ high - $ low ) / 2 ; if ( $ mid < $ high && $ arr [ $ mid + 1 ] < $ arr [ $ mid ] ) return ( int ) ( $ mid + 1 ) ; if ( $ mid > $ low && $ arr [ $ mid ] < $ arr [ $ mid - 1 ] ) return ( int ) ( $ mid ) ; if ( $ arr [ $ high ] > $ arr [ $ mid ] ) return countRotations ( $ arr , $ low , $ mid - 1 ) ; return countRotations ( $ arr , $ mid + 1 , $ high ) ; } $ arr = array ( 15 , 18 , 2 , 3 , 6 , 12 ) ; $ n = sizeof ( $ arr ) ; echo countRotations ( $ arr , 0 , $ n - 1 ) ; ? >