×

Search anything:

# Find K closest numbers to a given value

#### Algorithms binary search heap

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

### 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.

#### Aswin Shailajan

Aswin Shailajan is a B. Tech Computer Science student at Vellore Institute of Technology and is a SDE, Intern at OpenGenus.

Improved & Reviewed by:

Find K closest numbers to a given value