*We are given a sorted array, value V, and a number K. The value represents the number that may appear in the array, but it’s not mandatory. We are expected to find a set of size K, that contains the elements from the array, that are the closest to the value .*

The solution uses the famous **binary search** algorithm. Firstly we find the value V itself, or the closest to V, in the array. The latter, we obtain just as a result of a regular binary search, that returns the position of the element if it exists, or the position where it would appear. Let’s call this position P. We know that the element at position P, will be included in the result set. Now we need to consider the elements on the left and the right hand side of P. As the array is sorted, the closest element to the one on the position P, will lay on the position P-1, or P+1. We choose the one that is closer, and iteratively process till we fill the set to the expected size. An example code:

unsigned int binary_search(vector<int> array, int el){
unsigned int begin = 0;
unsigned int end = array.size() - 1;
unsigned int medium;
while(begin < end){
medium = begin + (end - begin)/2;
if(array < el)begin = medium + 1;
else end = medium;
}
return medium;
}
vector<int> get_k_closest(vector<int> array, int el, unsigned int k){
unsigned int split = binary_search(array, el);
int l = split, r = split + 1;
unsigned int counter = k;
vector<int> result;
while(counter){
if(l >= 0 && r < array.size()){
// choose the element that is closer
if(abs(array[l] - el) < abs(array[r] - el))
result.push_back(array[l--]);
else result.push_back(array[r++]);
} else {
if(l >= 0)
result.push_back(array[l--]);
else if(r < array.size())
result.push_back(array[r++]);
}
counter--;
}
return result;
}

### Like this:

Like Loading...

*Related*