design and implement a (nlogn) algorithm to determine the 'K' closest elements to a target value X in an array of 'n' integers. For example, consider an array A = {4, 1, 9, 7, 8, 3, 10, 2}. The three (K = 3) closest elements to integer 6 (X = 6) in this array are: {4, 7, 8}. If the target value X is in the array itself, then X is not to be considered as one of the K-Closest elements. For example, consider an array A = {4, 1, 9, 7, 8, 3, 10, 2}. The three (K = 3) closest elements to a target integer 7 (X = 7) in this array are: {4, 8, 9}. Note that {8, 9, 10} is also a valid answer in this case. As long as you print one of the valid answers, it is sufficient. In the above example (with {4, 8, 9} as the 3-closest values to '7'), the average of the 3-closest values is also 7, and the absolute difference between the target value of 7 and the average of the 3-closest values to 7 is 0. The 4-closest values to 7 are: {8, 9, 4, 10} and their average is 7.75; the absolute difference between the target value of 7 and the average of the 4-closest values to 7 is 0.75. Run simulations of your algorithm with array sizes of n = 100, 1000 and 10000. You could fill the arrays with integers randomly chosen from the range [1, ..., 500]. For each array size, vary the K values from 3 to 10. For each array size and K, conduct simulations for 50 runs (for each run, create an array for the given size and choose a random value for the target X in the range 1, ..., 500) and determine the average of the K-closest values to X as well as determine the overall average of the difference between the target X values and the average of the K-closest values to X (across the 50 simulation runs and the target X values chosen for a given array size and K). Also, determine the average execution time for each value of the array size and the different values of K.

(a) For each array size, n: plot the distribution of {K} vs. {overall average of the {difference between the target X values and the average of the K-closest values to the target X values} }

(b) For each array size, n: plot the distribution of {K} vs. average execution time. PLEASE PROVIDE CODE IN JAVA TO ENTER IN THE DIFFERENT VALUES FOR N AS ASKED IN THE QUESTION.

int findCrossOver(int arr[], int low, int high, int x)

{

// Base cases

if (arr[high] <= x) // x is greater than all

return high;

if (arr[low] > x) // x is smaller than all

return low;

// Find the middle point

int mid = (low + high)/2; /* low + (high - low)/2 */

/* If x is same as middle element, then return mid */

if (arr[mid] <= x && arr[mid+1] > x)

return mid;

/* If x is greater than arr[mid], then either arr[mid + 1]

is ceiling of x or ceiling lies in arr[mid+1...high] */

if(arr[mid] < x)

return findCrossOver(arr, mid+1, high, x);

return findCrossOver(arr, low, mid - 1, x);

}

// This function prints k closest elements to x in arr[].

// n is the number of elements in arr[]

void printKclosest(int arr[], int x, int k, int n)

{

// Find the crossover point

int l = findCrossOver(arr, 0, n-1, x);

int r = l+1; // Right index to search

int count = 0; // To keep track of count of elements

// already printed

// If x is present in arr[], then reduce left index

// Assumption: all elements in arr[] are distinct

if (arr[l] == x) l--;

// Compare elements on left and right of crossover

// point to find the k closest elements

while (l >= 0 && r < n && count < k)

{

if (x - arr[l] < arr[r] - x)

System.out.print(arr[l--]+" ");

else

System.out.print(arr[r++]+" ");

count++;

}

// If there are no more elements on right side, then

// print left elements

while (count < k && l >= 0)

{

System.out.print(arr[l--]+" ");

count++;

}

// If there are no more elements on left side, then

// print right elements

while (count < k && r < n)

{

System.out.print(arr[r++]+" ");

count++;

}

}

/* Driver program to check above functions */

public static void main(String args[])

{

KClosest ob = new KClosest();

int arr[] = {12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56

};

int n = arr.length;

int x = 35, k = 4;

ob.printKclosest(arr, x, 4, n);

}

} PLEASE EDIT THIS CODE SO IT CAN ANSWER THE QUESTION ASKED ABOVE