visual walkthrough
Find K Closest Elements
Binary search for the left edge of the best window.
The idea
The k closest values to x in a sorted array are always k neighbours in a row, so you only need to find where that window starts.
For a start mid, compare the window's first value with the value just after its end. Whichever is closer to x stays.
Complexity
| approach | time | space |
|---|---|---|
| Sort by distance | O(n log n) | O(n) |
| Binary search the window start | O(log(n − k) + k) | O(1) |