Find k closest elements to a given value | Function to find the cross over point ( the point before which elements aresmaller than or equal to x and afterwhich 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
def findCrossOver ( arr , low , high , x ) : NEW_LINE INDENT if ( arr [ high ] <= x ) : NEW_LINE INDENT return high NEW_LINE DEDENT if ( arr [ low ] > x ) : NEW_LINE INDENT return low NEW_LINE DEDENT mid = ( low + high ) // 2 NEW_LINE if ( arr [ mid ] <= x and arr [ mid + 1 ] > x ) : NEW_LINE INDENT return mid NEW_LINE DEDENT if ( arr [ mid ] < x ) : NEW_LINE INDENT return findCrossOver ( arr , mid + 1 , high , x ) NEW_LINE DEDENT return findCrossOver ( arr , low , mid - 1 , x ) NEW_LINE DEDENT def printKclosest ( arr , x , k , n ) : NEW_LINE INDENT l = findCrossOver ( arr , 0 , n - 1 , x ) NEW_LINE r = l + 1 NEW_LINE count = 0 NEW_LINE if ( arr [ l ] == x ) : NEW_LINE INDENT l -= 1 NEW_LINE DEDENT while ( l >= 0 and r < n and count < k ) : NEW_LINE INDENT if ( x - arr [ l ] < arr [ r ] - x ) : NEW_LINE INDENT print ( arr [ l ] , end = " ▁ " ) NEW_LINE l -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT print ( arr [ r ] , end = " ▁ " ) NEW_LINE r += 1 NEW_LINE DEDENT count += 1 NEW_LINE DEDENT while ( count < k and l >= 0 ) : NEW_LINE INDENT print ( arr [ l ] , end = " ▁ " ) NEW_LINE l -= 1 NEW_LINE count += 1 NEW_LINE DEDENT while ( count < k and r < n ) : NEW_LINE INDENT print ( arr [ r ] , end = " ▁ " ) NEW_LINE r += 1 NEW_LINE count += 1 NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 12 , 16 , 22 , 30 , 35 , 39 , 42 , 45 , 48 , 50 , 53 , 55 , 56 ] NEW_LINE n = len ( arr ) NEW_LINE x = 35 NEW_LINE k = 4 NEW_LINE printKclosest ( arr , x , 4 , n ) NEW_LINE DEDENT