Find k closest elements to a given value | Function to find the cross over point ( the point before which elements are smaller than or equal to x and after which greater than x ) ; Base cases x is greater than all ; x is smaller than all ; Find the middle point ; If x is same as middle element , then return mid ; If x is greater than arr [ mid ] , then either arr [ mid + 1 ] is ceiling of x or ceiling lies in arr [ mid + 1. . . high ] ; This function prints k closest elements to x in arr [ ] . n is the number of elements in arr [ ] ; Find the crossover point ; Right index to search ; To keep track of count of elements already printed ; If x is present in arr [ ] , then reduce left index Assumption : all elements in arr [ ] are distinct ; Compare elements on left and right of crossover point to find the k closest elements ; If there are no more elements on right side , then print left elements ; If there are no more elements on left side , then print right elements ; Driver Code
< ? php function findCrossOver ( $ arr , $ low , $ high , $ x ) { if ( $ arr [ $ high ] <= $ x ) return $ high ; if ( $ arr [ $ low ] > $ x ) return $ low ; $ mid = ( $ low + $ high ) / 2 ; if ( $ arr [ $ mid ] <= $ x and $ arr [ $ mid + 1 ] > $ x ) return $ mid ; if ( $ arr [ $ mid ] < $ x ) return findCrossOver ( $ arr , $ mid + 1 , $ high , $ x ) ; return findCrossOver ( $ arr , $ low , $ mid - 1 , $ x ) ; } function printKclosest ( $ arr , $ x , $ k , $ n ) { $ l = findCrossOver ( $ arr , 0 , $ n - 1 , $ x ) ; $ r = $ l + 1 ; $ count = 0 ; if ( $ arr [ $ l ] == $ x ) $ l -- ; while ( $ l >= 0 and $ r < $ n and $ count < $ k ) { if ( $ x - $ arr [ $ l ] < $ arr [ $ r ] - $ x ) echo $ arr [ $ l -- ] , " ▁ " ; else echo $ arr [ $ r ++ ] , " ▁ " ; $ count ++ ; } while ( $ count < $ k and $ l >= 0 ) echo $ arr [ $ l -- ] , " ▁ " ; $ count ++ ; while ( $ count < $ k and $ r < $ n ) echo $ arr [ $ r ++ ] ; $ count ++ ; } $ arr = array ( 12 , 16 , 22 , 30 , 35 , 39 , 42 , 45 , 48 , 50 , 53 , 55 , 56 ) ; $ n = count ( $ arr ) ; $ x = 35 ; $ k = 4 ; printKclosest ( $ arr , $ x , 4 , $ n ) ; ? >