题目重点：比较双指针扩张和固定长度窗口二分，解释判定单调性、平局方向和超大数组读取。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 数组升序可含重复，0≤k≤N；距离是绝对差，等距离优先较小数。训练代码返回有序切片。
- 题目未说明外存接口；本文只讨论索引/分块的前提，不声称普通 Python list 可装十亿级数据。
解题路线
- 可行答案必是长度 K 的连续窗口，否则两端间遗漏的更接近值可替换远端。于是只需确定左边界 L∈[0,N-K]。
- 设中点窗口 [mid,mid+K)。比较 x-A[mid] 与 A[mid+K]-x：若左端更远，窗口应右移；否则（包括相等）保留更左窗口。这个谓词沿候选左边界单调，二分得到最左优解。
- 备选法先二分 x 插入位置，再双指针向两边扩 K 次，比较距离并在平局时取左边；时间 O(log N+K)。窗口二分 O(log(N-K)+K)，且输出天然有序。
- 无序数组可用大小 K 的堆 O(N log K) 后排序，或 quickselect 平均 O(N) 再排序结果；外存有序数组若支持索引查找，可二分块元数据后读取邻近区间，若只能顺序流则不能声称随机访问复杂度。
手动走一遍
A=[1,2,3,4,5], x=3, k=4，候选 [1,2,3,4] 与 [2,3,4,5] 两端分别等距，按较小值优先选左窗口 [1,2,3,4]。k=0 返回空数组。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def k_closest_sorted(values: list[int], k: int, target: int) -> list[int]:
if k < 0 or k > len(values):
raise ValueError("invalid k")
left, right = 0, len(values) - k
while left < right:
mid = (left + right) // 2
# On equal distance, prefer the left window (smaller value).
if target - values[mid] > values[mid + k] - target:
left = mid + 1
else:
right = mid
return values[left:left + k]
复杂度
二分窗口 O(log(N-K+1)) 次随机访问，输出切片 O(K) 时间与 O(K) 输出空间；双指针 O(log N+K)。30,000 组随机有序数组与独立‘按距离/值排序取 K 后重排’参考模型一致。
易错点与追问
容易失分的边界
- 相等距离向右移，违反较小值优先。
- 二分只到 N-K+1 之外并访问 A[mid+K] 越界。
- 先取最近 K 个但忘记输出有序。
- 把无序数组也直接用窗口二分。
- 外存无索引却沿用 O(log N) 随机读取假设。
继续深挖
- 如果 x 位于所有数左侧或右侧？
- k 接近 N 时两种解法开销如何？
- 若距离平局优先较大值，判断如何改？
- 只提供顺序迭代器而无随机访问时能否小于 O(N)？
