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.
In the following solutions, it is assumed that all elements of array are distinct.
A simple solution is to do linear search for k closest elements.
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). This step takes O(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.
The time complexity of the above solution is O(n).
An Optimized Solution is to find k elements in O(Logn + k) time. The idea is to use Binary Search to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.
[ad type=”banner”]C++
[pastacode lang=”cpp” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F*%20Function%20to%20find%20the%20cross%20over%20point%20(the%20point%20before%0A%20%20%20which%20elements%20are%20smaller%20than%20or%20equal%20to%20x%20and%20after%0A%20%20%20which%20greater%20than%20x)*%2F%0Aint%20findCrossOver(int%20arr%5B%5D%2C%20int%20low%2C%20int%20high%2C%20int%20x)%0A%7B%0A%20%20%2F%2F%20Base%20cases%0A%20%20if%20(arr%5Bhigh%5D%20%3C%3D%20x)%20%2F%2F%20x%20is%20greater%20than%20all%0A%20%20%20%20return%20high%3B%0A%20%20if%20(arr%5Blow%5D%20%3E%20x)%20%20%2F%2F%20x%20is%20smaller%20than%20all%0A%20%20%20%20return%20low%3B%0A%20%0A%20%20%2F%2F%20Find%20the%20middle%20point%0A%20%20int%20mid%20%3D%20(low%20%2B%20high)%2F2%3B%20%20%2F*%20low%20%2B%20(high%20-%20low)%2F2%20*%2F%0A%20%0A%20%20%2F*%20If%20x%20is%20same%20as%20middle%20element%2C%20then%20return%20mid%20*%2F%0A%20%20if%20(arr%5Bmid%5D%20%3C%3D%20x%20%26%26%20arr%5Bmid%2B1%5D%20%3E%20x)%0A%20%20%20%20return%20mid%3B%0A%20%0A%20%20%2F*%20If%20x%20is%20greater%20than%20arr%5Bmid%5D%2C%20then%20either%20arr%5Bmid%20%2B%201%5D%0A%20%20%20%20is%20ceiling%20of%20x%20or%20ceiling%20lies%20in%20arr%5Bmid%2B1…high%5D%20*%2F%0A%20%20if(arr%5Bmid%5D%20%3C%20x)%0A%20%20%20%20%20%20return%20findCrossOver(arr%2C%20mid%2B1%2C%20high%2C%20x)%3B%0A%20%0A%20%20return%20findCrossOver(arr%2C%20low%2C%20mid%20-%201%2C%20x)%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20prints%20k%20closest%20elements%20to%20x%20in%20arr%5B%5D.%0A%2F%2F%20n%20is%20the%20number%20of%20elements%20in%20arr%5B%5D%0Avoid%20printKclosest(int%20arr%5B%5D%2C%20int%20x%2C%20int%20k%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20the%20crossover%20point%0A%20%20%20%20int%20l%20%3D%20findCrossOver(arr%2C%200%2C%20n-1%2C%20x)%3B%0A%20%20%20%20int%20r%20%3D%20l%2B1%3B%20%20%20%2F%2F%20Right%20index%20to%20search%0A%20%20%20%20int%20count%20%3D%200%3B%20%2F%2F%20To%20keep%20track%20of%20count%20of%20elements%20already%20printed%0A%20%0A%20%20%20%20%2F%2F%20If%20x%20is%20present%20in%20arr%5B%5D%2C%20then%20reduce%20left%20index%0A%20%20%20%20%2F%2F%20Assumption%3A%20all%20elements%20in%20arr%5B%5D%20are%20distinct%0A%20%20%20%20if%20(arr%5Bl%5D%20%3D%3D%20x)%20l–%3B%0A%20%0A%20%20%20%20%2F%2F%20Compare%20elements%20on%20left%20and%20right%20of%20crossover%0A%20%20%20%20%2F%2F%20point%20to%20find%20the%20k%20closest%20elements%0A%20%20%20%20while%20(l%20%3E%3D%200%20%26%26%20r%20%3C%20n%20%26%26%20count%20%3C%20k)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(x%20-%20arr%5Bl%5D%20%3C%20arr%5Br%5D%20-%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Bl–%5D)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Br%2B%2B%5D)%3B%0A%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20there%20are%20no%20more%20elements%20on%20right%20side%2C%20then%0A%20%20%20%20%2F%2F%20print%20left%20elements%0A%20%20%20%20while%20(count%20%3C%20k%20%26%26%20l%20%3E%3D%200)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Bl–%5D)%2C%20count%2B%2B%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20there%20are%20no%20more%20elements%20on%20left%20side%2C%20then%0A%20%20%20%20%2F%2F%20print%20right%20elements%0A%20%20%20%20while%20(count%20%3C%20k%20%26%26%20r%20%3C%20n)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Br%2B%2B%5D)%2C%20count%2B%2B%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20check%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20int%20arr%5B%5D%20%3D%7B12%2C%2016%2C%2022%2C%2030%2C%2035%2C%2039%2C%2042%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2045%2C%2048%2C%2050%2C%2053%2C%2055%2C%2056%7D%3B%0A%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20int%20x%20%3D%2035%2C%20k%20%3D%204%3B%0A%20%20%20printKclosest(arr%2C%20x%2C%204%2C%20n)%3B%0A%20%20%20return%200%3B%0A%7D” message=”c++” highlight=”” provider=”manual”/]JAVA
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20find%20k%20closest%20elements%20to%20a%20given%20value%0Aclass%20KClosest%0A%7B%0A%20%20%20%20%2F*%20Function%20to%20find%20the%20cross%20over%20point%20(the%20point%20before%0A%20%20%20%20%20%20%20which%20elements%20are%20smaller%20than%20or%20equal%20to%20x%20and%20after%0A%20%20%20%20%20%20%20which%20greater%20than%20x)*%2F%0A%20%20%20%20int%20findCrossOver(int%20arr%5B%5D%2C%20int%20low%2C%20int%20high%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20cases%0A%20%20%20%20%20%20%20%20if%20(arr%5Bhigh%5D%20%3C%3D%20x)%20%2F%2F%20x%20is%20greater%20than%20all%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20high%3B%0A%20%20%20%20%20%20%20%20if%20(arr%5Blow%5D%20%3E%20x)%20%20%2F%2F%20x%20is%20smaller%20than%20all%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20low%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20the%20middle%20point%0A%20%20%20%20%20%20%20%20int%20mid%20%3D%20(low%20%2B%20high)%2F2%3B%20%20%2F*%20low%20%2B%20(high%20-%20low)%2F2%20*%2F%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20x%20is%20same%20as%20middle%20element%2C%20then%20return%20mid%20*%2F%0A%20%20%20%20%20%20%20%20if%20(arr%5Bmid%5D%20%3C%3D%20x%20%26%26%20arr%5Bmid%2B1%5D%20%3E%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20mid%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20x%20is%20greater%20than%20arr%5Bmid%5D%2C%20then%20either%20arr%5Bmid%20%2B%201%5D%0A%20%20%20%20%20%20%20%20%20%20is%20ceiling%20of%20x%20or%20ceiling%20lies%20in%20arr%5Bmid%2B1…high%5D%20*%2F%0A%20%20%20%20%20%20%20%20if(arr%5Bmid%5D%20%3C%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20findCrossOver(arr%2C%20mid%2B1%2C%20high%2C%20x)%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20findCrossOver(arr%2C%20low%2C%20mid%20-%201%2C%20x)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20This%20function%20prints%20k%20closest%20elements%20to%20x%20in%20arr%5B%5D.%0A%20%20%20%20%2F%2F%20n%20is%20the%20number%20of%20elements%20in%20arr%5B%5D%0A%20%20%20%20void%20printKclosest(int%20arr%5B%5D%2C%20int%20x%2C%20int%20k%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20the%20crossover%20point%0A%20%20%20%20%20%20%20%20int%20l%20%3D%20findCrossOver(arr%2C%200%2C%20n-1%2C%20x)%3B%20%0A%20%20%20%20%20%20%20%20int%20r%20%3D%20l%2B1%3B%20%20%20%2F%2F%20Right%20index%20to%20search%0A%20%20%20%20%20%20%20%20int%20count%20%3D%200%3B%20%2F%2F%20To%20keep%20track%20of%20count%20of%20elements%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20already%20printed%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20x%20is%20present%20in%20arr%5B%5D%2C%20then%20reduce%20left%20index%0A%20%20%20%20%20%20%20%20%2F%2F%20Assumption%3A%20all%20elements%20in%20arr%5B%5D%20are%20distinct%0A%20%20%20%20%20%20%20%20if%20(arr%5Bl%5D%20%3D%3D%20x)%20l–%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Compare%20elements%20on%20left%20and%20right%20of%20crossover%0A%20%20%20%20%20%20%20%20%2F%2F%20point%20to%20find%20the%20k%20closest%20elements%0A%20%20%20%20%20%20%20%20while%20(l%20%3E%3D%200%20%26%26%20r%20%3C%20n%20%26%26%20count%20%3C%20k)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(x%20-%20arr%5Bl%5D%20%3C%20arr%5Br%5D%20-%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Bl–%5D%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Br%2B%2B%5D%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20there%20are%20no%20more%20elements%20on%20right%20side%2C%20then%0A%20%20%20%20%20%20%20%20%2F%2F%20print%20left%20elements%0A%20%20%20%20%20%20%20%20while%20(count%20%3C%20k%20%26%26%20l%20%3E%3D%200)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Bl–%5D%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20there%20are%20no%20more%20elements%20on%20left%20side%2C%20then%0A%20%20%20%20%20%20%20%20%2F%2F%20print%20right%20elements%0A%20%20%20%20%20%20%20%20while%20(count%20%3C%20k%20%26%26%20r%20%3C%20n)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Br%2B%2B%5D%2B%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20check%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20KClosest%20ob%20%3D%20new%20KClosest()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%2016%2C%2022%2C%2030%2C%2035%2C%2039%2C%2042%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2045%2C%2048%2C%2050%2C%2053%2C%2055%2C%2056%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20int%20x%20%3D%2035%2C%20k%20%3D%204%3B%0A%20%20%20%20%20%20%20%20ob.printKclosest(arr%2C%20x%2C%204%2C%20n)%3B%0A%20%20%20%20%7D%0A%7D” message=”java” highlight=”” provider=”manual”/]Output:
39 30 42 45
The time complexity of this method is O(Logn + k).
[ad type=”banner”]