Find K closest numbers to a given value

In this article, we will explore on how to find the K closest numbers to a given value in a given set of numbers. We have presented two approaches using the concepts of binary search and Heap data structure.

Pre-requisites

• Binary search
• Heaps

Problem Statement

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b

Example 1:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Observations

So from the question the observation is that the array is sorted. This will be the foundation of our optimal approach.

Approach 1

Here we will discuss the approach using heaps.

Intuitive Steps

• Create a priority queue of size k.
• Push elements into the queue as pairs:
  • first element - difference between element and x
  • second element - element itself
• Pop the top element whenever the size of the queue is greater than k.
• After iteration transfer the elements from the queue to a vector.
• Sort the vector.
• Display it.

Explained

• We need the closest elements to the k, so we will use a max heap. We will implement it using a priority queue.

• A priority queue is a container that is used to store and manipulate data items with a priority level assigned to each of them.

• It is a type of container adapter that uses a heap data structure to maintain the ordering of its elements. The elements are ordered based on their priority level, where the highest-priority element is always at the front of the queue.

• First, we will have a priority queue of pairs, we will store the the difference in the first and the number in the second.

• To store the numbers we will first iterate through the array and for each of the element we will do a push_back({abs(arr[i]-x), arr[i]}).

• We will keep an if statement inside the loop to check if the size of priority queue ever crosses the size k, if it does just pop the element. Since we need only the k elements we will pop() the rest.

• After this we will push all the elements in the priority_queue into a vector, then we will sort and display them.

Code:

#include <bits/stdc++.h>

using namespace std;

void findClosestElements(vector<int>& arr, int k, int x) {
        priority_queue<pair<int,int>>mh;
        vector<int>v;
        for(int i=0;i<arr.size();i++){
            mh.push({abs(arr[i]-x), arr[i]});
            if(mh.size()>k){
                mh.pop();
            }
        }
        while(mh.size()!=0){
            v.push_back(mh.top().second);
            mh.pop();
        }
        sort(v.begin(),v.end());
        for(int i=0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        return;
    }

int main() {
    int k,x,n;
    cout<<"Enter the number of elements: ";
    cin>>n;
    cout<<"Enter value for k and x respectively: ";
    cin>>k>>x;
    vector<int>v;
     cout<<"Enter "<<n<<" values: ";
    int i=0;
    while(i<n){
        int temp;
        i++;
        cin>>temp;
        v.push_back(temp);
    }

    findClosestElements(v, k, x);

    return 0;
}

The time complexity for the above approach will be O(nlogn) where n is the size of the array. The space complexity will be O(k).

Approach 2

Here we will use binary search to get the optimal solution.

Binary search is a searching algorithm that is used to find the position of a specific value in a sorted array. It works by repeatedly dividing the array into half, and then checking whether the value we are searching for is in the left half or the right half of the array. It then discards the half of the array that cannot contain the value we are searching for, and repeats the process until the value is found or the search is exhausted.

The time complexity of binary search is O(log n), where n is the number of elements in the array. This makes it a very efficient algorithm for searching large arrays. Overall, binary search is a powerful and widely-used algorithm that can be used in a variety of applications, such as searching databases, finding a specific value in a sorted list, or identifying the location of a specific record in a file.

Our goal is to use binary search to find the starting point of the solution.

Example:

If the array is: 11, 14, 15, 19, 22, 26, 27, 33, 36
k=5, x=26

The answer will be: 19, 22, 26, 27, 33

So here we will use binary search to find the starting point ie, 19, then we will take the starting point and k-1 elements to its right as the answer.

Intuitive Steps

• Our aim is to find the starting of our answer.
• Initialize lo = 0 and hi = n - k.
• Do the searching until lo < hi .
• Calculate mid inside the while loop.
• Move hi to mid when x-arr[mid] < arr[mid+k]-x.
• Move lo to mid + 1 when x-arr[mid] > arr[mid+k]-x.
• After while loop lo would be the starting point.
• The values from lo to lo + k would be the answer.

Explained

• First we will start our binary search with lo=0 and hi=n-k (n is the size of the vector)

• Since we have to take k elements from the starting point, hence we will take hi as n-k.

• So for each mid we are assuming it to be the starting value.

• Now to reduce the search space we will compare x-arr[mid] and arr[mid+k]-x.

  • If x-arr[mid] > arr[mid+k]-x that means the current mid can never be the candidate as its too low, so we will reduce the search space by making lo = mid+1.
  • If x-arr[mid] < arr[mid+k]-x that means that the mid could be a candidate so will will reduce the higher bound to find if any smaller elements are there which is closer to x than the current mid, and to do that we will make hi = mid.

• The moment lo>=hi the loop breaks and we have our starting point at lo, and we will take all the numbers from lo to lo+k into a new vector and display it or just display it directly.

Code:

#include <bits/stdc++.h>

using namespace std;

void findClosestElements(vector<int>& arr, int k, int x) {
        int lo=0, hi=arr.size()-k;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            if(x-arr[mid]>arr[mid+k]-x){
                lo=mid+1;
            }else hi=mid;
        }
        for(int i=0;i<k;i++){
            cout<<arr[lo+i]<<" ";
        }
        return;
    }

int main() {
    int k,x,n;
    cout<<"Enter the number of elements: ";
    cin>>n;
    cout<<"Enter value for k and x respectively: ";
    cin>>k>>x;
    vector<int>v;
    cout<<"Enter "<<n<<" values: ";
    int i=0;
    while(i<n){
        int temp;
        i++;
        cin>>temp;
        v.push_back(temp);
    }

    findClosestElements(v, k, x);

    return 0;
}

The time complexity for the above solution is O(log n) where n is the size of the array, and this program has a constant space complexity as no extra space is being used.

Output

Enter the number of elements: 5
Enter value for k and x respectively: 4 3
Enter 5 values: 1 2 3 4 5

1 2 3 4

With this article at OpenGenus, you must have the complete idea to find K closest numbers to a given value.