二分查找：最近的 K 个元素

Question

我尝试使用二分搜索方法解决 Leetcode 的“在排序数组中查找最近的 K 个元素”问题，但无法弄清楚为什么它不起作用。

LeetCode问题链接： 文字

问题描述：

给定一个排序整数数组

arr

、两个整数

k

和

x

，返回数组中与

k

最接近的整数

x

。结果也应该按升序排序。

整数

a

比整数

x

更接近

b

，如果：

• |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]

尝试编写程序来解决排序数组中 K 个最近的数字：

public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int startIndex = 0;
        int low = 0;
        int high = arr.length - k;
        int mid = -1;
        while(low <= high) {
            mid = low + (high - low)/2;
            if(x - arr[mid] > arr[mid + k - 1] - x) {
                low = mid + 1;
            }else {
                startIndex = mid;
                high = mid - 1;
            }
        }
        List<Integer> nearestKElements = new ArrayList<>();
        for(int i=startIndex; i<startIndex+k; i++){
            nearestKElements.add(arr[i]);
        }
        return nearestKElements;
}

即使对于简单的输入，上述程序也不起作用，例如：

输入： arr = [1,2,3,4,5], k = 4, x = 3

输出：[2,3,4,5]

预期输出：[1,2,3,4]

我发现上述方法的问题是，如果 arr[mid] 值与给定值的差异与 arr[mid + k - 1] 的差异相同，二分搜索应该采用哪条路径（左半部分或右半部分）从给定值。

x - arr[mid] == arr[mid + k - 1] - x

为了解决上述问题，我通过引入minimumDiff变量确保我永远不会覆盖迄今为止找到的最佳解决方案：

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int startIndex = 0;
        int low = 0;
        int high = arr.length - k;
        int mid = -1;
        int minimumDiff = Integer.MAX_VALUE;
        int diff = 0;
        while(low <= high) {
            mid = low + (high - low)/2;
            if(x - arr[mid] > arr[mid + k - 1] - x) {
                low = mid + 1;
                diff = x - arr[mid];
            }else {
                high = mid - 1;
                diff = arr[mid + k - 1] - x;
            }
            if(minimumDiff > diff) {
                minimumDiff = diff;
                startIndex = mid;
            }
        }
        List<Integer> nearestKElements = new ArrayList<>();
        for(int i=startIndex; i<startIndex+k; i++){
            nearestKElements.add(arr[i]);
        }
        return nearestKElements;
}

但是仍然输入失败：

输入：[0,0,1,2,3,3,4,7,7,8]，k = 3且x = 5

输出：[3,4,7]

预期输出：[3,3,4]

如果我们注意到，输出和预期输出的最大差异都是相同的，即：2

这是我发现的 leetcode 解决方案，它神奇地正确：

    public List<Integer> findClosestElements(int[] A, int k, int x) {
        int left = 0, right = A.length - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - A[mid] > A[mid + k] - x)
                left = mid + 1;
            else
                right = mid;
        }
        return Arrays.stream(A, left, left + k).boxed().collect(Collectors.toList());
    }

问题：

1. 在我的程序中，我将 arr[mid] 与候选窗口的最后一个元素（即 arr[mid + k -1] ）进行比较，但在 leetcode 解决方案中 arr[mid] 与 arr[mid+ k] 进行比较。为什么我们需要与 arr[mid + k] 进行比较？

2. 我知道有不同的模板来解决二分搜索程序。我正在使用“低<= high rather than low < high and saving best possible answer on each step". Can we solve this problem using this template ?

   ”的模板

Answer 1

您正在使用二分搜索来查找与

k

最接近的

x

元素的起点。总体思路是合理的，但问题在于二分搜索循环内的比较逻辑。

(1)问题1的答案

您需要将

arr[mid]

与

arr[mid + k]

进行比较，因为： 您正在尝试确定

k

元素的最佳“窗口”。 比较

x - arr[mid]

检查当前窗口的开始位置与

x

的接近程度。 比较

arr[mid + k] - x

检查当前窗口之外的元素与

x

的接近程度。

这很重要，因为

k

元素的窗口从

arr[mid]

跨越到

arr[mid + k - 1]

。与

arr[mid + k]

进行比较可确保您考虑向右扩展窗口是否会产生更好（更接近）的元素范围。如果

arr[mid + k]

比

x

更接近

arr[mid]

，那么您应该将窗口向右移动。

简而言之，比较可确保您选择尺寸最接近的窗口

k

。

(2)问题2的答案

是的，你可以用

low <= high

模板来解决，你的大体结构是正确的。 然而，问题在于循环内的边界条件和比较逻辑。

您当前正在将 arr[mid] 与

arr[mid + k - 1]

进行比较，这是不正确的，因为它错过了检查窗口外的元素

(arr[mid + k])

。如果您按如下方式调整比较，

low <= high

模板将起作用。