Find K Closest Elements: Binary Search the Answer Window
Solve Find K Closest Elements by binary-searching the best window start, with JavaScript code, a walkthrough, complexity, and tie-breaking details.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Find K Closest Elements looks like a selection problem: choose the k values nearest to x. That framing leads naturally to a heap or to repeatedly comparing individual elements. Both can work, but they miss the strongest fact in the prompt: the array is already sorted.
In a sorted array, the answer is a contiguous window. Once that is clear, the problem changes from “which k values do I choose?” to “where does the best length-k window begin?” The YeetCode visualizer makes that shift explicit by binary-searching the window start.
The problem
Given sorted arr, an integer k, and a target x, return the k closest integers to x in ascending order. When two values are equally far away, prefer the smaller value.
Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]There are n - k + 1 possible windows of length k. The result must be one of them. That contiguity is what lets binary search replace per-element selection.
The brute force baseline
One baseline sorts values by Math.abs(value - x), takes the first k, then sorts those values again for the required output order. It is understandable, but costs O(n log n) time and does extra work after the answer set is known.
Another approach expands two pointers around the insertion position of x. That is a sound O(log n + k) alternative, but it asks for one element at a time. The visualizer's approach instead compares two competing windows at a time and finds the start directly.
The key insight: compare window boundaries
For a candidate start mid, compare the value just outside the left side of its window with the value just outside the right side:
left distance = x - arr[mid]
right distance = arr[mid + k] - xIf x - arr[mid] > arr[mid + k] - x, the left outside value is worse than the right outside value. Sliding the window right improves the answer, so discard mid and everything left of it. Otherwise, keep the left side by setting right = mid.
The > is deliberate. On a tie, the left window contains the smaller numbers, which is exactly the problem's tie-break rule.
The optimal solution
function findClosestElements(arr, k, x) {
let left = 0;
let right = arr.length - k;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1;
} else {
right = mid;
}
}
return arr.slice(left, left + k);
}This matches the visualizer's canonical sequence: search starts in [0, n - k], compare the two window boundaries, then return arr[left:left + k]. Notice that mid + k is safe: mid is always below right, and right never exceeds n - k.
Walkthrough
For arr = [1, 2, 3, 4, 5], k = 4, and x = 3, starts 0 and 1 are possible.
| Step | left | right | mid | Compare | Decision |
|---|---|---|---|---|---|
| Start | 0 | 1 | 0 | 3 - 1 = 2 vs 5 - 3 = 2 | Tie: keep the left window |
| Update | 0 | 0 | — | Search ends | Window starts at 0 |
| Return | 0 | 0 | — | arr.slice(0, 4) | [1, 2, 3, 4] |
If the right-side distance had been smaller, left would move to mid + 1. Every iteration eliminates roughly half of the possible starts.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Sort by distance | O(n log n) | O(n) | Sorts all candidates |
| Two-pointer expansion | O(log n + k) | O(1), excluding output | Selects one result at a time |
| Binary search on start | O(log(n - k) + k) | O(1), excluding output | Searches windows, then copies k values |
The final slice creates the returned array, so if output space is counted the result itself uses O(k) space.
Common mistakes
- Binary-searching values instead of valid window starts
0throughn - k. - Using
>=in the comparison. That breaks the smaller-value tie rule by moving right on equal distances. - Comparing
arr[mid + k - 1]rather than the element just beyond the candidate window,arr[mid + k]. - Returning a window sorted by distance instead of the ascending subarray the prompt requires.
Where this pattern shows up next
- Sqrt(x) uses binary search over a monotonic answer space.
- Binary Search establishes the boundary-update discipline used here.
- Guess Number Higher or Lower is the simplest form of discarding an impossible half.
- Search in Rotated Sorted Array shows how to recover a sorted half before making that discard.
You can step through Find K Closest Elements interactively to see the candidate window shift.
FAQ
Why are the closest elements always a contiguous window?
In sorted order, if two selected values sit on either side of an unselected value, that middle value cannot be farther from x than both selected values. Replacing the farther selected endpoint with it never hurts, so an optimal selection can be made contiguous.
Why does a tie keep the left window?
When the distances x - arr[mid] and arr[mid + k] - x are equal, the left candidate includes the smaller boundary value. The prompt requires smaller values first in a distance tie, so the algorithm sets right = mid rather than moving left.
Is the binary-search solution better than a heap?
For a sorted array, usually yes: it exploits order and only searches n - k + 1 window positions. A heap is useful when values arrive unsorted or as a stream, but it does not use the contiguous-window property available here.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.