Monday, March 9, 2015

Find k closest elements to a given value (not finished yet...)

Given a sorted array arr[] and a value X, find the k closest elements to X in arr[]. 
Examples:
Input: K = 4, X = 35
       arr[] = {12, 16, 22, 30, 35, 39, 42, 
               45, 48, 50, 53, 55, 56}
Output: 30 39 42 45
Note that if the element is present in array, then it should not be in output, only the other closest elements are required.
Assume that all elements of array are distinct.

Solution:
1) Use Binary Search to find the crossover point. This step takes O(log n) time.
2) Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.

No comments:

Post a Comment