题目

题目来源：力扣（LeetCode）

给定一个排序好的数组 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]

思路分析

使用二分法，始终对长度为k的连续子数组进行操作，最终确定起点位置，即左端点

  1. 初始时，将区间左边界 left 设为 0，区间右边界 right 设为 arr.length - 1
  2. 通过二分法取得区间的中间值 mid

  3. 然后比较长度为 k + 1 的区间的左右端点的数值与 x 的差值的绝对值:

    • 假设此时这个区间的左边界的下标是 mid，右边界的下标是 mid + k
    • 如果右边界与 x 的差值的绝对值较小，左边界收缩，即 left = mid + 1
    • 如果左边界与 x 的差值的绝对值较小，右边界收缩，即 right = mid ```javascript /**
    • @param {number[]} arr
    • @param {number} k
    • @param {number} x
    • @return {number[]} */ // 二分法，始终对长度为k的连续子数组进行操作，最终确定起点位置即可，即左端点 var findClosestElements = function (arr, k, x) { // 初始时，区间左边界 left 为 0，区间右边界 right 为 length - 1 let left = 0, right = arr.length - 1; while (left < right) { // 二分查找取中间值 const mid = left + Math.floor((right - left) / 2); // 比较长度为 k + 1 的区间的左右端点的数值与 x 的差值的绝对值 // 假设此时这个区间的左边界的下标是 mid，右边界的下标是 mid + k // 如果右边界与 x 的差值的绝对值较小，左边界收缩，即 left = mid + 1 // 如果左边界与 x 的差值的绝对值较小，右边界收缩，即 right = mid if (x - arr[mid] > arr[mid + k] - x) { left = mid + 1; } else { right = mid; } }

    return arr.slice(left, left + k) } ```