Get this book > Problems on Array: For Interviews and Competitive Programming
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.
Prerequisites
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
, ora  x == b  x
anda < 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
 first element  difference between element and
 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 amax heap
. We will implement it using apriority 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 highestpriority 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 thesecond
. 
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 sizek
, if it does just pop the element. Since we need only thek
elements we willpop()
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 widelyused 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 k1 elements to its right as the answer.
Intuitive Steps
 Our aim is to find the starting of our answer.
 Initialize
lo = 0
andhi = n  k
.  Do the searching until
lo < hi
.  Calculate
mid
inside thewhile
loop.  Move
hi
tomid
whenxarr[mid] < arr[mid+k]x
.  Move
lo
tomid + 1
whenxarr[mid] > arr[mid+k]x
.  After while loop
lo
would be the starting point.  The values from
lo
tolo + k
would be the answer.
Explained

First we will start our binary search with
lo=0
andhi=nk
(n
is the size of the vector) 
Since we have to take
k
elements from the starting point, hence we will takehi
asnk
. 
So for each
mid
we are assuming it to be the starting value. 
Now to reduce the search space we will compare
xarr[mid]
andarr[mid+k]x
. If
xarr[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 makinglo = mid+1
.  If
xarr[mid] < arr[mid+k]x
that means that themid
could be a candidate so will will reduce the higher bound to find if any smaller elements are there which is closer tox
than the currentmid
, and to do that we will makehi = mid
.
 If

The moment
lo>=hi
the loop breaks and we have our starting point atlo
, and we will take all the numbers fromlo
tolo+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+(hilo)/2;
if(xarr[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.