Find K Closest Elements: Binary Search Window

Find K Closest Elements is LeetCode 658, and it is a great example of how binary search can do more than just find a single value. Instead of searching for a target in a sorted array, you are searching for the best starting position of a sliding window. The array is already sorted, and you need to find the k elements closest to a given value x. The key insight is that you do not need to compute distances for every possible window. You can binary search for the left boundary of the optimal window in O(log(n - k)) time.

The problem

You are given a sorted integer array arr, two integers k and x. Return the k closest integers to x in the array. The result should also be sorted in ascending order.

If two integers are equally close to x, the smaller one is considered closer. The answer is always a contiguous subarray of length k in the sorted input.

Example: arr = [1, 2, 3, 4, 5], k = 4, x = 3. The four closest elements to 3 are [1, 2, 3, 4].

Because the array is sorted, the k closest elements always form a contiguous window. That is the property that makes binary search possible. You are not picking k arbitrary elements. You are finding where the window of size k should start.

Why binary search on the left boundary works

Think about it this way. The answer is a subarray arr[left..left+k-1]. The left boundary can range from 0 to n - k. For any candidate left boundary mid, you can check whether the window should shift right by comparing the distance from x to the element just outside the left edge (arr[mid]) versus the element just outside the right edge (arr[mid + k]).

If x - arr[mid] is greater than arr[mid + k] - x, the element at mid + k is closer to x than the element at mid. That means the window is too far left, and you should move right. Otherwise, the window is fine where it is or needs to move left.

This comparison gives you a monotonic condition. Once the window is far enough right, it stays right. That is exactly the structure binary search needs.

Step-by-step walkthrough

Let's trace through arr = [1, 2, 3, 4, 5, 6, 7], k = 3, x = 5. The valid range for the left boundary is 0 to 4 (since n - k = 7 - 3 = 4).

Three steps, and we found the answer. The binary search narrows the range of valid left boundaries until only one remains. At each step, the distance comparison tells us which direction to move.

The code

Here is the complete Python solution for LeetCode 658:

def find_closest_elements(arr, k, x):
    lo, hi = 0, len(arr) - k

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if x - arr[mid] > arr[mid + k] - x:
            lo = mid + 1
        else:
            hi = mid

    return arr[lo:lo + k]

The search space is [0, n - k], the range of valid left boundaries. At each step, mid is a candidate left boundary. You compare the distance from x to the left edge of the window (x - arr[mid]) against the distance to the element just past the right edge (arr[mid + k] - x). If the right side is closer, the window needs to shift right, so you set lo = mid + 1. Otherwise, you keep the current position as a candidate and set hi = mid. When lo == hi, you have found the optimal left boundary.

Note the comparison uses strict greater-than (>), not greater-than-or-equal. This ensures that when distances are tied, we prefer the smaller element (keeping the window further left), which matches the problem's tie-breaking rule.

Complexity analysis

The binary search runs in O(log(n - k)) iterations with O(1) work per iteration. Building the output slice takes O(k). For most inputs, log(n - k) is much smaller than n, so this is a significant improvement over the O(n) sliding window approach.

The building blocks

Binary search on a window boundary

This problem uses a variant of binary search where the search space is not the array values themselves, but the set of valid starting positions for a subarray. The template looks like this:

lo, hi = 0, len(arr) - k

while lo < hi:
    mid = lo + (hi - lo) // 2
    if should_move_right(mid):
        lo = mid + 1
    else:
        hi = mid

return lo

The same structure appears whenever you need to find the optimal position for a fixed-size window in a sorted array. The only thing that changes is the should_move_right condition. In this problem, it is a distance comparison. In other problems, it might be a sum comparison or a different metric.

If you are comfortable with the standard binary search template from problems like Binary Search (LeetCode 704), this is a natural extension. The loop structure (while lo < hi, hi = mid, lo = mid + 1) is identical. The only new idea is that you are searching over window positions instead of array values.

Edge cases

• x is smaller than all elements: The closest k elements are the first k elements. The binary search naturally converges to lo = 0.
• x is larger than all elements: The closest k elements are the last k elements. The search converges to lo = n - k.
• x is in the array: Works the same way. The search finds the window that includes x and its nearest neighbors.
• k equals n: There is only one possible window (the entire array). lo = 0, hi = 0, and the loop never runs.
• Duplicate values: The distance comparison handles duplicates correctly. Equal distances favor the left position due to the strict > comparison.

From understanding to recall

The binary search window approach is elegant, but the details matter. Is it x - arr[mid] > arr[mid + k] - x or >=? Is the upper bound n - k or n - k - 1? These small choices determine whether your solution handles ties correctly and whether the loop terminates.

Spaced repetition helps you lock in these details. You write the solution from scratch today, then again in two days, then in a week. After a few rounds, the comparison direction and the boundary formula become automatic. You do not have to rederive them under interview pressure.

LeetCode 658 is an excellent SRS candidate because the code is compact (about 7 lines), the pattern generalizes to other window-based binary search problems, and the tie-breaking logic is easy to get wrong if you have not practiced it recently.

Related posts

• Binary Search (LeetCode 704) - The foundational binary search template that this problem builds on
• Find First and Last Position of Element in Sorted Array - Another binary search variant where you control which direction the search collapses toward
• Koko Eating Bananas - Binary search on the answer space, a related pattern where you search a range of candidate values instead of array indices

Ready to build lasting fluency with binary search patterns? Practice this problem and dozens more with spaced repetition that adapts to your progress.