Find k closest elements to a given value | Java program to 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 program to check above functions
class KClosest { int findCrossOver ( int arr [ ] , int low , int high , int x ) { if ( arr [ high ] <= x ) return high ; if ( arr [ low ] > x ) return low ; int mid = ( low + high ) / 2 ; if ( arr [ mid ] <= x && arr [ mid + 1 ] > x ) return mid ; if ( arr [ mid ] < x ) return findCrossOver ( arr , mid + 1 , high , x ) ; return findCrossOver ( arr , low , mid - 1 , x ) ; } void printKclosest ( int arr [ ] , int x , int k , int n ) { int l = findCrossOver ( arr , 0 , n - 1 , x ) ; int r = l + 1 ; int count = 0 ; if ( arr [ l ] == x ) l -- ; while ( l >= 0 && r < n && count < k ) { if ( x - arr [ l ] < arr [ r ] - x ) System . out . print ( arr [ l -- ] + " ▁ " ) ; else System . out . print ( arr [ r ++ ] + " ▁ " ) ; count ++ ; } while ( count < k && l >= 0 ) { System . out . print ( arr [ l -- ] + " ▁ " ) ; count ++ ; } while ( count < k && r < n ) { System . out . print ( arr [ r ++ ] + " ▁ " ) ; count ++ ; } } public static void main ( String args [ ] ) { KClosest ob = new KClosest ( ) ; int arr [ ] = { 12 , 16 , 22 , 30 , 35 , 39 , 42 , 45 , 48 , 50 , 53 , 55 , 56 } ; int n = arr . length ; int x = 35 , k = 4 ; ob . printKclosest ( arr , x , 4 , n ) ; } }