{"id":25246,"date":"2017-10-15T16:21:50","date_gmt":"2017-10-15T10:51:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25246"},"modified":"2017-10-15T16:21:50","modified_gmt":"2017-10-15T10:51:50","slug":"find-k-closest-elements-given-value","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-k-closest-elements-given-value\/","title":{"rendered":"Find k closest elements to a given value"},"content":{"rendered":"

Given a sorted array arr[] and a value X, find the k closest elements to X in arr[]. <\/span>
\nExamples:<\/p>\n

Input: K = 4, X = 35\r\n       arr[] = {12, 16, 22, 30, 35, 39, 42, \r\n               45, 48, 50, 53, 55, 56}\r\nOutput: 30 39 42 45\r\n<\/pre>\n
Note that if the element is present in array, then it should not be in output, only the other closest elements are required.<\/p>\n
In the following solutions, it is assumed that all elements of array are distinct.<\/p>\n
A simple solution <\/strong>is to do linear search for k closest elements.
\n1) 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.
\n2) 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.<\/p>\n
The time complexity of the above solution is O(n).<\/p>\n
An Optimized Solution<\/strong> is to find k elements in O(Logn + k) time. The idea is to use Binary Search<\/a> to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.<\/p>\n[ad type=\u201dbanner\u201d]\n
C++<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u2026high%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\u2013%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\u2013%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\u2013%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\u201d message=\u201dc++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
JAVA<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%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\u2026high%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\u2013%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\u2013%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\u2013%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\u201d message=\u201djava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
39 30 42 45<\/pre>\n
The time complexity of this method is O(Logn + k).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Find k closest elements to a given value – searching and sorting – 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). <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670],"tags":[72525,72561,72515,72521,72541,72558,72518,72536,72545,72553,72551,72537,72522,72529,72548,72528,72538,72546,72520,72516,72517,72524,72569,72542,72567,72547,72530,72519,72565,72555,72559,72533,72531,72556,72560,72523,72550,72539,72552,72570,72568,72571,72540,72544,72532,72566,72526,72557,72554,72534,72562,72564,72543,72563,72527,72535,72549,72572],"class_list":["post-25246","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","tag-ball-tree","tag-data-mining-knn","tag-find-k-closest-elements-to-a-given-value","tag-find-neighbors","tag-k-nearest","tag-k-nearest-neighbor","tag-k-nearest-neighbor-algorithm","tag-k-nearest-neighbor-algorithm-example","tag-k-nearest-neighbor-classification","tag-k-nearest-neighbor-classification-algorithm","tag-k-nearest-neighbor-classification-in-data-mining","tag-k-nearest-neighbor-classifier","tag-k-nearest-neighbor-example","tag-k-nearest-neighbor-python","tag-k-nearest-neighbor-python-code","tag-k-nearest-neighbors-algorithm","tag-k-nearest-neighbour-algorithm-in-data-mining","tag-k-nearest-neighbour-example-in-data-mining","tag-k-nearest-neighbours","tag-knn","tag-knn-algorithm","tag-knn-algorithm-example","tag-knn-algorithm-implementation","tag-knn-algorithm-in-data-mining","tag-knn-algorithm-pseudocode","tag-knn-algorithm-python","tag-knn-classification","tag-knn-classifier","tag-knn-classifier-algorithm","tag-knn-classifier-example","tag-knn-classifier-python","tag-knn-data-mining","tag-knn-example","tag-knn-in-data-mining","tag-knn-method","tag-knn-python","tag-knn-python-code","tag-knn-r","tag-knnsearch","tag-nearest","tag-nearest-neighbor","tag-nearest-neighbor-algorithm","tag-nearest-neighbor-algorithm-example","tag-nearest-neighbor-classification","tag-nearest-neighbor-classifier","tag-nearest-neighbor-example","tag-nearest-neighbor-search","tag-nearest-neighbour-algorithm-in-data-mining","tag-nearest-neighbour-classification","tag-nearest-neighbour-classifier","tag-nearest-neighbour-in-data-mining","tag-neighbor-finder","tag-neighborhood-search","tag-neighbors-1","tag-python-knn","tag-python-nearest-neighbor","tag-r-knn","tag-tree-ball"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25246","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25246"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25246\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}