题目

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

示例 1:

  1. 输入: [1,2,3,4,5], k=4, x=3
  2. 输出: [1,2,3,4]

示例 2:

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

说明:

  • k 的值为正数，且总是小于给定排序数组的长度。
  • 数组不为空，且长度不超过 $10^4$
  • 数组里的每个元素与 x 的绝对值不超过 $10^4$

方案一

func findClosestIndex(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    var left, right = 0, len(nums) - 1
    for left + 1 < right {
        var mid = (left + right) / 2
        // 获取差值的绝对值
        var diff = nums[mid] - target
        if diff == 0 {
            return mid
        } else if diff > 0 {
            right = mid
        } else {
            left = mid
        }
    }

    // Post-processing:
    // End Condition: left + 1 == right
    if target - nums[left] <= nums[right] - target {
        return left
    } else {
        return right
    }
}

func findClosestElements(arr []int, k int, x int) []int {
    if x <= arr[0] {
        return arr[:k]
    }
    if x >= arr[len(arr)-1] {
        return arr[len(arr)-k:]
    }

    var i = findClosestIndex(arr, x)
    var left, right = i, i + 1
    for right-left < k {
        left -= 1
        right += 1
        if left < 0 {
            return arr[:k]
        }
        if right > len(arr) {
            return arr[len(arr)-k:]
        }
        if x-arr[left] <= arr[right - 1]-x {
            right -= 1
        } else {
            left += 1
        }

        // if left - 1 <= 0 { // left 指针已经到第一个
        //     return arr[:k]
        // }
        // if right + 1 >= len(arr) - 1 { // right 指针已经到数组尾
        //     return arr[len(arr) - k:]
        // }
        // if x - arr[left] <= arr[right] - x {
        //     left -= 1
        // } else {
        //     right += 1
        // }
    }

    return arr[left:right]
}

步骤：

  1. 先用二分查找（模板三）找到最近的索引
  2. 再往左右拓展寻找目标范围

注意：

  1. 注释部分是错误的代码，本来想正向考虑，即当条件成功时才移动 left/right 指针，结果怎么也调不好（老是数组越界，硬要判断代码太难看）；所以想到了上述的，先移动指针，然后判断数组越界问题，最后将多移动的指针移回来。
  2. 二分查找时，如果要使用 数组 的相邻元素作为判断条件，注意使用 模板三

原文

https://leetcode-cn.com/explore/learn/card/binary-search/211/template-iii/845/