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
Method:
1) Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). We will use Binary search for this.This step takes O(logn) 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.
Time: For k elements it takes O(Logn + k) time.
http://www.geeksforgeeks.org/find-k-closest-elements-given-value/
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
Method:
1) Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). We will use Binary search for this.This step takes O(logn) 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.
Time: For k elements it takes O(Logn + k) time.
http://www.geeksforgeeks.org/find-k-closest-elements-given-value/
No comments:
Post a Comment