# 2.找到 K 个最接近的元素（middle）
# 一、题目
LeetCode658.找到 K 个最接近的元素 (opens new window)
给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3 输出：[1,2,3,4] 示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1 输出：[1,2,3,4]
提示：
1 <= k <= arr.length 1 <= arr.length <= 104 数组里的每个元素与 x 的绝对值不超过 104
# 二、基础模版 III
因为我们的判断区间最少为 2 个元素，所以我们要注意循环的执行条件
- 简单的判断边界：
nums.length === 0，return -1； - 定义初始的左右边界：
left = 0, right = nums.length - 1； - 确定执行条件：
left + 1 < right，这也意味着查找区间要存在 3 个元素； - 向左查找时：
right = mid； - 向左查找时：
left = mid； - 判断剩下的两个元素哪个符合目标元素，并返回结果；
# 三、题解
分析模版
- 我们的目标是：寻找目标值的起始下标和终止下标，但它是可能重复的
- 针对这样的情况，我们要将判断拆解成查找目标首次出现的位置，和最后一次出现的位置
JavaScript 代码
var findClosestElements = function(arr, k, x) {
let left = 0;
let right = arr.length - k; // 注意我们让出来k的值，当作我们的“备用值”
let res = [];
while (left < right) {
let mid = left + ((right - left) >> 1);
if (x - arr[mid] > arr[mid + k] - x) {
// x-arr[mid] > arr[mid+k]-x，arr[mid+k]的点一定距离目标值更近
// 且它距离arr[mid]是k个，证明arr[mid]一定不会存在与结果区间中，它也不可能是起始点
left = mid + 1; // 我们在移动满足条件的起始点
} else {
// x-arr[mid] <= arr[mid+k]-x，arr[mid]下标的点一定距离目标值更近
// 所以我们需要收缩右边界
right = mid; // 压缩右区间
}
}
for (let i = left; i < left + k; i++) {
res.push(arr[i]);
}
return res;
};
# 四、写在最后
本文是二分查找-模版III 的第最后一题，我会在之后将二分法的常见问题整理成完成的文档，我们一起加油～
如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励
关于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虚心学习中
其他沉淀
