Find K Closest Elements
The key idea
The answer is always a contiguous window of
k elements (the array is sorted, so the closest values sit next to each other). So we only need to find the window's left index lo. Binary-search lo over [0, n - k]: compare the distance of the element just left of the window, x - arr[mid], against the element just past it, arr[mid + k] - x. If the left edge is strictly farther, slide the window right; otherwise the left edge is at least as good, so keep it. A non-strict tie keeps the smaller side, matching the tie rule.Problem
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.
An integer a is closer to x than an integer b if |a - x| < |b - x|, or |a - x| == |b - x| and a < b. In other words, on a tie the smaller value is preferred.
Constraints
1 <= k <= arr.length1 <= arr.length <= 10^4arris sorted in ascending order-10^4 <= arr[i], x <= 10^4
Examples
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]
Input: arr = [1,3,5,7,9,11], k = 3, x = 6
Output: [3,5,7]
Complexity
Time: O(log(n - k) + k) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD
- Search a 2D MatrixMEDIUM