二叉搜索求解"排序矩阵中的第 K 个最小元素"。如何确保算法的正确性，

Question

我指的是leetcode问题：排序矩阵中的第k个最小元素

这个问题有两种众所周知的解决方案。一个使用Heap/PriorityQueue，另一个使用二进制搜索。二叉搜索解决方案是这样的(顶部帖子(：

public class Solution {
public int kthSmallest(int[][] matrix, int k) {
    int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi)
    while(lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 0,  j = matrix[0].length - 1;
        for(int i = 0; i < matrix.length; i++) {
            while(j >= 0 && matrix[i][j] > mid) j--;
            count += (j + 1);
        }
        if(count < k) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
}

虽然我了解这是如何工作的，但我很难弄清楚一个问题。我们如何确定返回的lo始终在矩阵中？

由于搜索空间是min的，并且max数组的值，因此mid不必是数组中的值。但是，返回的lo始终是。

为什么会这样？

Answer 1

为了论证，我们可以将count的计算移动到一个单独的函数中，如下所示：

bool valid(int mid, int[][] matrix, int k) {
    int count = 0, m = matrix.length;
    for (int i = 0; i < m; i++) {
        int j = 0;
        while (j < m && matrix[i][j] <= mid) j++;
        count += j;
    }
    return (count < k);
}

此谓词将执行与指定操作完全相同的操作。在这里，循环不变性是，范围[lo, hi]始终包含 2D 数组中kth最小的数字。

换句话说，lo <= solution <= hi

现在，当循环终止时，很明显lo >= hi

合并这两个属性，我们得到，lo = solution = hi，因为solution是数组的成员，可以说，lo总是在循环终止后在数组中，并且会正确地指向kth最小的元素。

Answer 2

因为我们使用二叉搜索找到lower_bound，数组中不可能有任何小于数字(lo(的数字，这可能是第k个最小的元素。