{"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=”banner”]\n
C++<\/strong><\/p>\n
 
 c++<\/span> <\/div> 
#include<stdio.h> \/* Function to find the cross over point (the point before   which elements are smaller than or equal to x and after   which greater than x)*\/int findCrossOver(int arr[], int low, int high, int x){  \/\/ Base cases  if (arr[high] <= x) \/\/ x is greater than all    return high;  if (arr[low] > x)  \/\/ x is smaller than all    return low;   \/\/ Find the middle point  int mid = (low + high)\/2;  \/* low + (high - low)\/2 *\/   \/* If x is same as middle element, then return mid *\/  if (arr[mid] <= x && arr[mid+1] > x)    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] *\/  if(arr[mid] < x)      return findCrossOver(arr, mid+1, high, x);   return findCrossOver(arr, low, mid - 1, x);} \/\/ This function prints k closest elements to x in arr[].\/\/ n is the number of elements in arr[]void printKclosest(int arr[], int x, int k, int n){    \/\/ Find the crossover point    int l = findCrossOver(arr, 0, n-1, x);    int r = l+1;   \/\/ Right index to search    int count = 0; \/\/ 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    if (arr[l] == x) l--;     \/\/ Compare elements on left and right of crossover    \/\/ point to find the k closest elements    while (l >= 0 && r < n && count < k)    {        if (x - arr[l] < arr[r] - x)            printf("%d ", arr[l--]);        else            printf("%d ", arr[r++]);        count++;    }     \/\/ If there are no more elements on right side, then    \/\/ print left elements    while (count < k && l >= 0)        printf("%d ", arr[l--]), count++;     \/\/ If there are no more elements on left side, then    \/\/ print right elements    while (count < k && r < n)        printf("%d ", arr[r++]), count++;} \/* Driver program to check above functions *\/int main(){   int arr[] ={12, 16, 22, 30, 35, 39, 42,               45, 48, 50, 53, 55, 56};   int n = sizeof(arr)\/sizeof(arr[0]);   int x = 35, k = 4;   printKclosest(arr, x, 4, n);   return 0;}<\/code><\/pre> <\/div>\n
JAVA<\/strong><\/p>\n
 
 java<\/span> <\/div> 
\/\/ Java program to find k closest elements to a given valueclass KClosest{    \/* Function to find the cross over point (the point before       which elements are smaller than or equal to x and after       which greater than x)*\/    int findCrossOver(int arr[], int low, int high, int x)    {        \/\/ Base cases        if (arr[high] <= x) \/\/ x is greater than all            return high;        if (arr[low] > x)  \/\/ x is smaller than all            return low;         \/\/ Find the middle point        int mid = (low + high)\/2;  \/* low + (high - low)\/2 *\/         \/* If x is same as middle element, then return mid *\/        if (arr[mid] <= x && arr[mid+1] > x)            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] *\/        if(arr[mid] < x)            return findCrossOver(arr, mid+1, high, x);         return findCrossOver(arr, low, mid - 1, x);    }     \/\/ This function prints k closest elements to x in arr[].    \/\/ n is the number of elements in arr[]    void printKclosest(int arr[], int x, int k, int n)    {        \/\/ Find the crossover point        int l = findCrossOver(arr, 0, n-1, x);         int r = l+1;   \/\/ Right index to search        int count = 0; \/\/ 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        if (arr[l] == x) l--;         \/\/ Compare elements on left and right of crossover        \/\/ point to find the k closest elements        while (l >= 0 && r < n && count < k)        {            if (x - arr[l] < arr[r] - x)                System.out.print(arr[l--]+" ");            else                System.out.print(arr[r++]+" ");            count++;        }         \/\/ If there are no more elements on right side, then        \/\/ print left elements        while (count < k && l >= 0)        {            System.out.print(arr[l--]+" ");            count++;        }          \/\/ If there are no more elements on left side, then        \/\/ print right elements        while (count < k && r < n)        {            System.out.print(arr[r++]+" ");            count++;        }    }     \/* Driver program to check above functions *\/    public static void main(String args[])    {        KClosest ob = new KClosest();        int arr[] = {12, 16, 22, 30, 35, 39, 42,                     45, 48, 50, 53, 55, 56                    };        int n = arr.length;        int x = 35, k = 4;        ob.printKclosest(arr, x, 4, n);    }}<\/code><\/pre> <\/div>\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=”banner”]\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}]}}