Problem Statement:
Given a sorted array, this algorithm returns the k elements closest to a target value x. The output is sorted in ascending order.
Approach:
- We apply
binary search to find the best starting indexof the k closest elements window. - We compare
arr[m + k] - xandx - arr[m]to decide whether to shift the window left or right. - Once we find the optimal window, return the subarray from index
ltol + k - 1.
Time & Space Complexity:
Time Complexity: O(log(n – k) + k)
Space Complexity: O(k)
Dry Run
Input (assumed): arr = [1, 3, 5, 6, 4, 2], k = 3, x = 5
Initial: l = 0, r = arr.length - k = 6 - 3 = 3 --- While Loop Execution --- Loop 1: m = l + Math.floor((r - l) / 2) = 0 + Math.floor((3 - 0) / 2) = 1 arr[m + k] = arr[1 + 3] = arr[4] = 4 arr[m] = arr[1] = 3 Compute comparisons: (arr[m + k] - x) = 4 - 5 = -1 (x - arr[m]) = 5 - 3 = 2 Check: (arr[m + k] - x) < (x - arr[m]) → -1 < 2 → true Action: l = m + 1 = 2 Loop 2: l = 2, r = 3 m = 2 + Math.floor((3 - 2) / 2) = 2 arr[m + k] = arr[2 + 3] = arr[5] = 2 arr[m] = arr[2] = 5 Compute comparisons: (arr[m + k] - x) = 2 - 5 = -3 (x - arr[m]) = 5 - 5 = 0 Check: -3 < 0 → true Action: l = m + 1 = 3 Exit Condition: l = 3, r = 3 → loop ends Build answer: Take elements from index l to l + k - 1: indices 3, 4, 5 → arr[3] = 6, arr[4] = 4, arr[5] = 2 ans = [6, 4, 2] --- Final Result --- Function returns: [6, 4, 2] Note: The algorithm assumes arr is sorted (non-decreasing). Using an unsorted array (like the input above) still runs, but results may not match the intended "k closest elements" semantics for sorted inputs.
Output: Result: [6, 4, 2]
var findClosestElements = function(arr, k, x) {
let l = 0;
let r = arr.length - k;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if ((arr[m + k] - x) < (x - arr[m])) {
l = m + 1;
} else {
r = m;
}
}
let ans = [];
for(let i = l; i < l + k; i++) {
ans.push(arr[i]);
}
return ans;
};
def findClosestElements(arr, k, x):
l, r = 0, len(arr) - k
while l < r:
m = l + (r - l) // 2
if x - arr[m] > arr[m + k] - x:
l = m + 1
else:
r = m
return arr[l:l + k]
public List findClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.length - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x)
l = m + 1;
else
r = m;
}
List res = new ArrayList<>();
for (int i = l; i < l + k; i++)
res.add(arr[i]);
return res;
}
vector findClosestElements(vector& arr, int k, int x) {
int l = 0, r = arr.size() - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x) {
l = m + 1;
} else {
r = m;
}
}
return vector(arr.begin() + l, arr.begin() + l + k);
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
int l = 0, r = arrSize - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x)
l = m + 1;
else
r = m;
}
int* res = (int*)malloc(k * sizeof(int));
for (int i = 0; i < k; ++i)
res[i] = arr[l + i];
*returnSize = k;
return res;
}
public IList FindClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.Length - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x)
l = m + 1;
else
r = m;
}
List result = new List();
for (int i = l; i < l + k; i++)
result.Add(arr[i]);
return result;
}
