二分查找实现LeetCode最接近K个元素问题遇错求助

你的核心问题出在差值相等时的处理逻辑，以及条件判断的错误，导致测试用例arr=[1,2,3,4,4,4,4,5,5], k=3, x=3出现错误结果。

问题分析 #

• 无效的越界判断：你代码里的(mid + k < arr.length)完全多余，因为初始high = arr.length - k，所以mid的最大值是arr.length -k，mid +k最多等于arr.length，不会越界。这个条件会错误地触发low = mid +1，直接打乱二分逻辑。
• 差值相等时的错误处理：当x - arr[mid] == arr[mid +k] -x时，题目要求取较小的数，也就是应该选择更靠左的区间，此时应该移动high = mid -1，而不是左移。你当前的逻辑在这种情况下去了右半区间，导致选中了[4,4,4]而不是正确的[2,3,4]。
• 多余的minimumDiff变量：二分查找的本质就是直接定位正确的起始位置，不需要额外记录最小差值来更新起始索引，二分结束后low就是正确的起始点。

修正后的代码 #

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    int low = 0;
    int high = arr.length - k;
    // 二分查找正确的起始位置
    while (low < high) {
        int mid = low + (high - low) / 2;
        // 比较区间左端点和区间右端点的下一个元素与x的差值
        if (x - arr[mid] > arr[mid + k] - x) {
            // 右边的区间更优，移动左指针
            low = mid + 1;
        } else {
            // 左边的区间更优（包括差值相等的情况），移动右指针
            high = mid;
        }
    }
    // 从low开始取k个元素
    List<Integer> result = new ArrayList<>();
    for (int i = low; i < low + k; i++) {
        result.add(arr[i]);
    }
    return result;
}

逻辑解释 #

• 二分的目标是找到长度为k的区间的起始索引：每次比较arr[mid]（当前区间左端点）和arr[mid+k]（当前区间右端点的下一个元素）与x的差值。
  • 如果x - arr[mid] > arr[mid+k] -x：说明右边的元素更接近x，需要把区间往右移，所以low = mid +1。
  • 否则（包括差值相等的情况）：说明左边的元素更优（或者相等时选更小的），所以把区间往左移，high = mid。
• 循环结束时low == high，就是正确的起始位置，直接取从low开始的k个元素即可。

测试你给出的用例，这段代码会返回正确的[2,3,4]。

内容的提问来源于stack exchange，提问作者user3036345