如何用二分查找找到有序数组中最接近目标的 K 个元素？

简化版

在有序数组中找最接近 x 的 k 个元素，可以二分答案窗口的左端点。

窗口长度固定为 k，左端点范围是 [0, n-k]。比较 x - arr[mid] 和 arr[mid+k] - x，判断更好的窗口在左边还是右边。

最后得到的窗口 [left, left+k) 就是答案。

详细版

因为数组有序，最终答案一定是连续的一段长度为 k 的窗口。

设窗口左端点为 l，候选窗口是：

arr[l ... l+k-1]

比较相邻窗口时，本质是在比较应该丢左端还是右端：

if x - arr[mid] > arr[mid + k] - x:
  left = mid + 1
else:
  right = mid

比较结果	含义
左端离 x 更远	窗口右移
右端离 x 更远或相等	保留更靠左窗口

复杂度是 O(log(n-k) + k)。

完整版教学

1. 为什么答案是连续窗口

数组已经有序。

如果选中的元素中间漏掉了某个更靠近 x 的元素，却选择了更远的外侧元素，就不可能最优。

所以最终 k 个元素在有序数组中一定构成连续片段。

有序数组里的“最近 K 个元素”不是任意集合，而是一个长度为 K 的窗口。

2. 暴力扩展怎么做

一种直观方法是先找到 x 的插入位置，然后用双指针向左右扩展。

这种方法可行，复杂度大约是：

O(log n + k)

但还有一种很优雅的方式：直接二分窗口左端点。

3. 为什么能二分窗口左端点

窗口长度固定为 k。

左端点最小是 0，最大是 n-k。

left in [0, n-k]

当窗口太靠左时，应该右移；当窗口太靠右时，应该左移。这个方向具有单调性，因此可以二分。

4. 比较 arr[mid] 和 arr[mid+k] 的含义

考虑两个相邻窗口：

窗口 A: [mid, mid+k-1]
窗口 B: [mid+1, mid+k]

它们中间 k-1 个元素相同，区别只在：

• A 包含 arr[mid]；
• B 包含 arr[mid+k]。

所以只需要比较这两个端点谁离 x 更远。

5. 为什么条件是 x - arr[mid] > arr[mid+k] - x

如果：

x - arr[mid] > arr[mid+k] - x

说明左端元素比右侧新元素更远，窗口应该右移。

否则窗口不应该右移，保留更靠左的可能答案。

相等时通常选择更小元素，所以让 right = mid。

6. 代码模板怎么写

伪代码：

left = 0
right = n - k
while left < right:
  mid = left + (right - left) / 2
  if x - arr[mid] > arr[mid + k] - x:
    left = mid + 1
  else:
    right = mid
return arr[left : left + k]

注意 mid + k 不会越界，因为 right <= n-k。

7. 边界情况有哪些

情况	结果
x 小于所有元素	返回前 k 个
x 大于所有元素	返回后 k 个
距离相等	通常选更小元素
k == n	返回整个数组

二分窗口模板能自然处理这些边界。

8. 常见误区与追问

• 误区：最近 K 个元素可能分散在数组各处。 在有序数组中，它们一定是连续窗口。
• 误区：比较窗口要逐个元素比较。 相邻窗口只差两个端点，比较端点即可。
• 误区：相等时随便选。 题目通常要求更小元素优先，所以相等时保留左窗口。
• 追问：复杂度是多少？ 二分左端点 O(log(n-k))，输出答案 O(k)。
• 追问：为什么 mid+k 不越界？ 左端点搜索范围是 [0, n-k]，所以 mid+k <= n。