Find the k-closest elements to a given value in a sorted array

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;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s