Двоичный поиск, чтобы решить "Kth самый маленький элемент в отсортированной матрице". Как можно обеспечить правильность алгоритма,

Question

Я имею в виду вопрос о Leetcode: Kth самый маленький элемент в отсортированной матрице

Есть два известных решения этой проблемы. Один использует 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

Потому что мы находим нижнюю границу с помощью двоичного поиска, и в массиве не может быть никакого числа меньше числа (lo), которое могло бы быть k-м наименьшим элементом.

Answer 2

Ради аргумента, мы можем переместить расчет 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] всегда содержит kth наименьшее число двумерного массива.

Другими словами, lo <= solution <= hi

Теперь, когда цикл заканчивается, очевидно, что lo >= hi

Объединяя эти два свойства, мы получаем, lo = solution = hi, поскольку solution является членом массива, можно сказать, что lo всегда находится в массиве после завершения цикла и будет правильно указывать на kth самый маленький элемент.