# Find k closest elements of number x in a sorted array

 Category: Data Structure And Algorithms Tags:

## Problem

Given numbers k and x, find k closest numbers to x in a sorted array where x may be present or not in array. If x is present we have to exclude it from solution.

Example 1

array={2,3,5,8,10}, k=3 and x=6.

Output = {5,8,3}

Example 2

array={2,4,6,8,9}, k=2 and x=6.

Output = {4,8}

Example 3

array={2,3,5,8,9}, k=2 and x=1.

Output = {2,3}

## Solution

Since array is sorted we can find one of the closest element which we call crossing element. Once crossing element is found we can look at right and left directions for remaining closest elements.

As in example1 we have crossing element is 5 and next closest element to x(x=6) could be at right side or left side of 5 so we compare both with x. (6-3) > (8-6) so next closest element is 8. We will use binary search to find closest element.

```static int FindClosestCrossingElement(int[] array, int n, int start, int end)
{
if (n <= array[start])
return start;

if (n >= array[end])
return end;

int mid = (start + end) / 2;

if (n == array[mid])
return mid;

if (n > array[mid])
return FindClosestCrossingElement(array, n, mid + 1, end);
else
return FindClosestCrossingElement(array, n, start, mid - 1);
}```

Once closest element is found we can write method to find all closest elements.

```static List<int> GetKClosestNumbers(int[] array, int x, int k, int closestElement)
{
List<int> result = new List<int>();

// If item present in array we have to exclude it else we can include closest element in output
int i = array[closestElement] == x ? closestElement - 1 : closestElement;
int j = closestElement + 1;

while (k > 0 && i >= 0 && j < array.Length)
{
int differenceWithPrevElement = Math.Abs(x - array[i]);
int differenceWithNextElement = Math.Abs(x - array[j]);
// Direction of i is left and direction of j is right
if (differenceWithPrevElement < differenceWithNextElement)
{
i--;
}
else
{
j++;
}
k--;
}
// If i reached zero then only one direction we can move is right
while (i > 0 && k > 0)
{
i--;
k--;
}
// If j reached end of array then only one direction we can move is left
while (j < array.Length && k > 0)
{
j++;
k--;
}
return result;
}```

Go through code and comments to understand the method. Lets print k closest elements.

```static void Main(string[] args)
{
int[] array = new int[] { 2, 3, 5, 8, 10 };
int x = 6;
int k = 3;

var closestElement = FindClosestCrossingElement(array, x, 0, array.Length - 1);
var kClosestNumbers = GetKClosestNumbers(array, x, k, closestElement);

foreach (int i in kClosestNumbers)
Console.WriteLine(i);
}```

Output

8
5
3

 Like 0 People
 Nikhil Joshi Ceo & Founder at Dotnetlovers Atricles: 158 Questions: 16 Given Best Solutions: 16 *