Let's start by understanding the problem statement of this task.
You are given with the sorted array, your work is to find the k closest elements to a given value.
Hint:
For searching for the k closest elements in the sorted array we can use the binary search to search for the index which has an element close to the given value and then searches for the other k elements around the given value from both left and the right side except for the value itself, one can also use the linear search, but it has a time complexity of O(n) but the binary search approach has a time complexity of O(logn + k).
Quick Think:
For finding the midpoint of the array from where the searching for the other elements which are closest to the given value we will follow the following steps:-
- Carry out the binary search and find the midpoint by the logic that if the given element is the greatest of all, then return the index of the last element.
- If the given element is the smallest of all elements in the array, then return the index of the first element in the array.
- Also, if the current mid-element is less than the given element in the array, then search for the subarray from the start index to the one index less than the mid-element’s index as the closest k elements will be present in the following subarray.
- Else, search in the subarray from the index one greater than the index of the mid-element’s index, as the closest k elements will be found at that subarray.
Algorithm:
Create a function to select the mid-index of the subarray with arguments as the array, the start index of the array, the last index of the array and the given element and then follow the below algorithm to find the index of the mid-element in the array.
Step1: Check if the element in the last index is less than the given element, if yes then return the index of the last element in the array, else go to step 2.
Step2: Check if the element in the start index of the array is greater than the given element, if yes then return the index of the starting element in the array else go to step 3.
Step3: Calculate the mid-index of the array or the subarray by the relation mid = start + (last - start) / 2.
Step4: Check if the element at mid of the array is less than or equal to the given element if yes then recursively call the function with arguments as the array, the mid + 1 as the start index and the last index as the last index of the array and the given element.
Create a function to find the k elements from the sorted array with the arguments of the array, the given element, the number of elements to be chosen and the total size of the array and then follow the following steps to print the k elements of the array.
Step1: Define a variable with the value of the left index as the mid-index of the subarray and the right index as the next index of the mid-index, and initialize count to 0.
Step2: Check if the current mid-element is the given element or not, if yes then decrement the mid-index by one else go to step 3.
Step3: Now keep checking the elements in the array which are close to the given element by imposing the condition as the no of elements to be selected should be less than the k value and the left index must be equal to or greater than 0 and the right index must be less than the total size of the array.
Step4: Keep checking for the left and the right elements in the array if the difference of the array element from the left side is less than the difference to the right side then keep printing the left array elements else keep printing the right side elements and keep incrementing the count variable.
Step5: If still there are any left or the right element left to be printed, then keep printing them by traversing through the array once again for both left and the right side separately.
Implementation Of The Above Algorithm:
Now let's see the implementation of the above algorithm,
#include <bits/stdc++.h>
using namespace std;
/*Function to find the mid index of the sorted array. */
int binarysearch(int arr[], int low, int high, int key)
{
/*If the given element is the greatest then return the index of the last element. */
if (arr[high] <= key)
return high;
/*If the given element is the smallest then return the index of the first element. */
if (arr[low] > key)
return low;
/*Calculate the mid of the array. */
int mid = low + (high - low) / 2;
if (arr[mid] <= key && arr[mid + 1] > key)
return mid;
/*If the given element is larger than the mid element of the array then traverse the right subarray. */
if (arr[mid] < key)
return binarysearch(arr, mid + 1, high, key);
/*Else traverse the left subarray. */
return binarysearch(arr, low, mid - 1, key);
}
void printelements(int arr[], int n, int k, int key)
{
int left = binarysearch(arr, 0, n - 1, key);
int right = left + 1;
int count = 0;
if (arr[left] == key)
left--;
/*Keep printing the elements closest to the given element. */
while (count < k && left >= 0 && right < n)
{
if (key - arr[left] < arr[right] - key)
cout << arr[left--] << " ";
else
cout << arr[right++] << " ";
count++;
}
/*Keep printing the left out elements in left subarray. */
while (count < k && left >= 0)
{
cout << arr[left--] << " ";
count++;
}
/*Keep printing the left out elements in right subarray. */
while (count < k && right < n)
{
cout << arr[right++] << " ";
count++;
}
}
/*Driver program to check above functions */
int main()
{
int arr[] = { 10, 21, 37, 40, 50, 60, 70 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 37, k = 4;
printelements(arr, n, 4, x);
return 0;
}
Time Complexity Of The Above Algorithm is O(logn + k).
The Output Of The Above Algorithm is 40 50 21 60.
Explanation Of The Above Algorithm:
Let us take an example of the above array, as shown in the diagram.
To find all the four closest elements to the given value 37 in the above algorithm, we will follow the following steps:-
- Find the mid-index of the above array as here we have low = 0 and high = 6, hence since 37 is not the largest neither the smallest in the given array, hence we calculate mid which will be equal to 3 as shown in the above diagram.
- Now, the mid-element in the array is greater than the given element, so we take the subarray with
low = 0 and high = 2.
- Hence, again calculate the mid, we get mid = 1, as shown in the above diagram.
- Now since this value is less than the given element 37 hence, we will take the subarray as low = 2 and high = 6.
- Again, calculate the mid of the subarray which is 4, hence the element at index 4 is greater than the given element.
- Hence, now we will take the subarray with low = 0 and high = 3, now the value of mid will be 2 as shown in the above diagram.
- Now the value of mid is returned and left variable is set to 2 and the right variable is set to 3 and count variable to 0.
- Now, since the element at index 2 is equal to the given value 37 hence, the value of left is re-declared as 1.
- Now moving on to the next loop we see that the difference between the given element and the left element is not smaller than the difference between the right index element and the given element 37 and so, the right index element gets printed and 40 is printed first and count is incremented to 1 and right variable to 4 as shown in the above diagram.
- Now similarly following the steps we get that the difference between the given element and the left element is not smaller than the difference between the right index element and the given element 37 and so, the right index element gets printed and 50 is printed and count is incremented to 2 and right variable to 5 as shown in the above diagram.
- And similarly now the difference between the given element and the left element is smaller than the difference between the right index element and the given element 37 and so, the left index element gets printed and 21 is printed, and the count is incremented to 3 and left variable to 2 as shown in the above diagram.
