Search an element in a sorted and rotated array | Returns index of key in arr [ l . . h ] if key is present , otherwise returns - 1 ; If arr [ l ... mid ] is sorted ; As this subarray is sorted , we can quickly check if key lies in half or other half ; If key not lies in first half subarray , Divide other half into two subarrays , such that we can quickly check if key lies in other half ; If arr [ l . . mid ] is not sorted , then arr [ mid ... r ] must be sorted ; Driver Code
< ? php function search ( $ arr , $ l , $ h , $ key ) { if ( $ l > $ h ) return -1 ; $ mid = ( $ l + $ h ) / 2 ; if ( $ arr [ $ mid ] == $ key ) return $ mid ; if ( $ arr [ $ l ] <= $ arr [ $ mid ] ) { if ( $ key >= $ arr [ $ l ] && $ key <= $ arr [ $ mid ] ) return search ( $ arr , $ l , $ mid - 1 , $ key ) ; return search ( $ arr , $ mid + 1 , $ h , $ key ) ; } if ( $ key >= $ arr [ $ mid ] && $ key <= $ arr [ $ h ] ) return search ( $ arr , $ mid + 1 , $ h , $ key ) ; return search ( $ arr , $ l , $ mid - 1 , $ key ) ; } $ arr = array ( 4 , 5 , 6 , 7 , 8 , 9 , 1 , 2 , 3 ) ; $ n = sizeof ( $ arr ) ; $ key = 6 ; $ i = search ( $ arr , 0 , $ n - 1 , $ key ) ; if ( $ i != -1 ) echo " Index : ▁ " , floor ( $ i ) , " ▁ STRNEWLINE " ; else echo " Key ▁ not ▁ found " ; ? >