In **Finding K closest element** problem we have given a sorted array and a value x. The problem is to find the K number of elements closest to x in the given array.

Given an array arr[] ={12, 16, 22, 30, 35, 39, 42,45, 48, 50, 53, 55, 56} and x = 35. Your task is to find the k=4 closest element to x.

Result: 30,39,42,45

Note that if x is in the array then it will be skipped in the output.

Table of Contents

## Algorithm

- Declare and define a binary search method.
- Declare a function solution in which
**array[], x, and k**are passed as an argument from the main function. - Call a binary search function from solution function, which returns the position of
**x to cp**in solution function. - Set
**n**to array length, left to**cp-1**, right to**cp+1**, and count to 0. - Iterates in the while loop, over the array till the following condition, satisfies:
- left>=0 and
- right < n and
- count < k

- Open if block in while loop, in which conditions are given as:
- x – array[left]
- array[right] – x

- If satisfies the condition, then print
**array[left]**and do**left —**. - If above condition failed then print
**array[right]**and do**right++**and do**count++**inside the loop. - Open if block with conditions given as if
**(right = = n )**, open the while loop with conditions given as**count < k**and**left >= 0**if satisfies , then print**array[left]**and do**count++**. - Again open second if block with conditions given as if
**(left < 0 )**, open the while loop with conditions given as**count < k**and**left >= 0**, if satisfies, then print**array[right]**and do**count++**.

The approach behind is we will first do a binary search to find the point nearest index to **x**. Then, we will search left and right for K closest element.

## Explanation for Finding K closest element

So we have our first task as we have to find the ‘k’ closest elements to x in the array which is sorted and all gonna make our task easier. For this, we can use a binary search method to find out the element position, with that our task becomes easier to find k closest elements.

So our main idea is to obtain the position of x and do some operations and find out the number with the least difference with x in the given array. For this, we are going to pass the arguments of arr[], x, and k. Arguments like arr, 0, length of the array, and the number of which we have to find the position are passed into a binary search function from which we obtain the value of the position. With this position we are going to set the value of left to just before the x and value of the right to just after the x, that is left = cp -1( just before the x) and right to cp+1 (just after the x).

Now if arr[left], means the number just before the x has a difference( x – arr[left] ) less than ( arr[right] –x ), means the number just after the x then print the value of arr[left] and do left–, for the next time, else print arr[right] and keep increasing the value od count by 1.

## Example

Suppose array given:

arr={12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};

x=35, we got the position as 4 of 35.

Here left = cp -1 = 3 and right = cp + 1 = 5

Therefore, we compare x – arr[left] < arr[right] – x => 5 < 4, which fails the condition,

So in else block it will print arr[right] that is 39 and do right++ and count++ that is count=1.

Now left = 3 and right becomes 6

So we compare x – arr[left] < arr[right] – x => 5 < 7, which is true condition,

So in if block it will print arr[left] that is 30 and do left– and count++ that is count=2.

Now left=2 and right =6

So we compare x – arr[left] < arr[right] – x => 13 < 7, which is true condition,

So in else block it will print arr[right] that is 42 and do right++ and count++ that is count=3.

Now left=2 and right=7

So we compare x – arr[left] < arr[right] – x => 13 < 7, which fails the condition,

So in if else it will print arr[right] that is 42 and do right++ and count++ that is count=4.

And now our count condition is failed means we got our all k closest elements.

And we have the answer as [39 30 42 45].

## Implementation

### C++ Program for Finding K closest element

#include<stdio.h> int Binary_Search(int arr[], int low, int high, int x) { int mid = (low + high)/2; if (arr[high] <= x) return high; if (arr[low] > x) return low; if (arr[mid] <= x && arr[mid+1] > x) return mid; if(arr[mid] < x) return Binary_Search(arr, mid+1, high, x); return Binary_Search(arr, low, mid - 1, x); } void solution(int arr[], int x, int k, int num) { int y = Binary_Search(arr, 0, num-1, x); int r = y+1; int count = 0; if (arr[y] == x) y--; while (y >= 0 && r < num && count < k) { if (x - arr[y] < arr[r] - x) printf("%d ", arr[y--]); else printf("%d ", arr[r++]); count++; } while (count < k && y >= 0) printf("%d ", arr[y--]), count++; while (count < k && r < num) printf("%d ", arr[r++]), count++; } int main() { int arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}; int num = sizeof(arr)/sizeof(arr[0]); int x = 35; int k = 4; solution(arr, x, k, num); return 0; }

39 30 42 45

### Java Program for Finding K closest element

public class kce { public static int binarySearch(int[] arr,int low, int high, int x){ int mid = 0; while(low<=high){ mid = (high+low)/2; if(arr[mid] == x){ return mid; } else if(x<arr[mid]){ high = mid-1; } else{ low = mid+1; } } return mid; } public static void solution(int[] arr,int x, int k){ int cp = binarySearch(arr, 0, arr.length-1, x); int n = arr.length-1; int left = cp-1; int right = cp+1; int count = 0; while(left>=0 && right<n && count <k){ if(x-arr[left]< arr[right] -x){ System.out.print(arr[left--] + " "); left--; } else{ System.out.print(arr[right++] + " "); right++; } count++; } if(right == n){ while(count<k && left>=0){ System.out.print(arr[left] + " "); count++; } } if(left < 0){ while(count<k && left>=0){ System.out.print(arr[right] + " "); count++; } } } public static void main(String[]args){ int k = 4; int x = 35; int arr1[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}; solution(arr1,x,k); } }

39 30 45 50

## Complexity Analysis

### Time Complexity

**O(Logn+ K)** where **“n”** is the size of the array and **“k”** is the number of the closest element we have to find.

### Space Complexity

**O(k)** to store the required number of the closest elements.