C++ Programming Code Examples C++ > Sorting Searching Code Examples Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers Program to Find k Numbers Closest to Median of S, Where S is a Set of n Numbers - We need to find k numbers which have a minimum difference with the median of the data set. - It includes sorting using quick sort and then printing k numbers as a result. - The time complexity will be O(n*log(n)+k). - Take input of the data. - Sort the data using the quick-sort algorithm. - Starting from the median index, using two variable moves towards the end of the array. - compare each value to the median and print those which are closer to it. - Repeat this k time printing the k numbers closest to the median. - Exit. #include<iostream> using namespace std; // Swapping two values. void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } // Partitioning the array on the basis of values at high as pivot value. int Partition(int a[], int low, int high) { int pivot, index, i; index = low; pivot = high; // Getting index of pivot. for(i=low; i < high; i++) { if(a[i] < a[pivot]) { swap(&a[i], &a[index]); index++; } } // Swapping value at high and at the index obtained. swap(&a[pivot], &a[index]); return index; } // Implementing QuickSort algorithm. int QuickSort(int a[], int low, int high) { int pindex; if(low < high) { // Partitioning array using randomized pivot. pindex = Partition(a, low, high); // Recursively implementing QuickSort. QuickSort(a, low, pindex-1); QuickSort(a, pindex+1, high); } return 0; } int main() { int n, i, high, low, k; double d1,d2, median; cout<<"Enter the number of element in dataset: "; cin>>n; int a[n]; // Taking input of the data set. for(i = 0; i < n; i++) { cout<<"\nEnter "<<i+1<<"th element: "; cin>>a[i]; } cout<<"\nEnter the number of element nearest to the median required: "; cin>>k; // Sort the data. QuickSort(a, 0, n-1); //Print the result. cout<<"\tThe K element nearest to the median are: "; // Check the number of data element to be even or odd and proceed accordingly. if(n%2 == 1) { median = a[n/2]; high = n/2+1; low = n/2; // Loop to search for the next element generating minimum difference from median. while(k > 0) { // If difference from the first half element is minimum. if((median-a[low] <= a[high]-median) && low >= 0) { cout<<" "<<a[low]; low--; k--; } // If difference from the Second half element is minimum. else if((median-a[low] > a[high]-median) && high <= n-1) { cout<<" "<<a[high]; high++; k--; } } } else { // Need to use floating variable since the median can be in the fractional form. d1 = a[n/2]; d2 = a[n/2-1]; median = (d1+d2)/2; high = n/2; low = n/2-1; while(k > 0) { d1 = a[low]; d2 = a[high]; // If difference from the first half element is minimum. if((median-d2 <= d1-median) && low >= 0) { cout<<" "<<a[low]; low--; k--; } // If difference from the Second half element is minimum. else if((median-d2 > d1-median) && high <= n-1) { cout<<" "<<a[high]; high++; k--; } } } return 0; }