Find k closest numbers in sorted array

Find k closest elements of number x in a sorted array


Category: Data Structure And Algorithms Tags: C#

Find k closest numbers in sorted array - Code Files

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)
        {
            result.Add(array[i]);
            i--;
        }
        else
        {
            result.Add(array[j]);
            j++;
        }
        k--;
    }
    // If i reached zero then only one direction we can move is right
    while (i > 0 && k > 0)
    {
        result.Add(array[i]);
        i--;
        k--;
    }
    // If j reached end of array then only one direction we can move is left
    while (j < array.Length && k > 0)
    {
        result.Add(array[j]);
        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
Last modified on 10 March 2022
Nikhil Joshi

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

Comments:

No Comments Yet

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x