Search in an almost sorted array | A recursive binary search based function . It returns index of x in given array arr [ l . . r ] is present , otherwise - 1 ; If the element is present at one of the middle 3 positions ; If element is smaller than mid , then it can only be present in left subarray ; Else the element can only be present in right subarray ; We reach here when element is not present in array ; Driver Code
< ? php function binarySearch ( $ arr , $ l , $ r , $ x ) { if ( $ r >= $ l ) { $ mid = $ l + ( $ r - $ l ) / 2 ; if ( $ arr [ $ mid ] == $ x ) return $ mid ; if ( $ mid > $ l && $ arr [ $ mid - 1 ] == $ x ) return ( $ mid - 1 ) ; if ( $ mid < $ r && $ arr [ $ mid + 1 ] == $ x ) return ( $ mid + 1 ) ; if ( $ arr [ $ mid ] > $ x ) return binarySearch ( $ arr , $ l , $ mid - 2 , $ x ) ; return binarySearch ( $ arr , $ mid + 2 , $ r , $ x ) ; } return -1 ; } $ arr = array ( 3 , 2 , 10 , 4 , 40 ) ; $ n = sizeof ( $ arr ) ; $ x = 4 ; $ result = binarySearch ( $ arr , 0 , $ n - 1 , $ x ) ; if ( $ result == -1 ) echo ( " Element ▁ is ▁ not ▁ present ▁ in ▁ array " ) ; else echo ( " Element ▁ is ▁ present ▁ at ▁ index ▁ $ result " ) ; ? >