Бинарный поисковый запрос: поиск записи мидиана в двух отсортированных массивах

Question

Существует два отсортированных массива nums1 и nums2 размера m и n соответственно.Найдите медиану двух отсортированных массивов.Общая сложность времени выполнения должна быть O (log (m + n)).

Пример 1: nums1 = [1, 3] nums2 = [2]

Медиана составляет 2,0

Пример 2: nums1 = [1, 2] nums2 = [3, 4]

Медиана: (2 + 3) / 2 = 2,5

public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // Deal with invalid corner case. 
    if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0.0;

    int m = nums1.length, n = nums2.length;
    int l = (m + n + 1) / 2; //left half of the combined median
    int r = (m + n + 2) / 2; //right half of the combined median

    // If the nums1.length + nums2.length is odd, the 2 function will return the same number
    // Else if nums1.length + nums2.length is even, the 2 function will return the left number and right number that make up a median
    return (getKth(nums1, 0, nums2, 0, l) + getKth(nums1, 0, nums2, 0, r)) / 2.0;
}

private double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
    // This function finds the Kth element in nums1 + nums2

    // If nums1 is exhausted, return kth number in nums2
    if (start1 > nums1.length - 1) return nums2[start2 + k - 1];

    // If nums2 is exhausted, return kth number in nums1
    if (start2 > nums2.length - 1) return nums1[start1 + k - 1];

    // If k == 1, return the first number
    // Since nums1 and nums2 is sorted, the smaller one among the start point of nums1 and nums2 is the first one
    if (k == 1) return Math.min(nums1[start1], nums2[start2]);

    int mid1 = Integer.MAX_VALUE;
    int mid2 = Integer.MAX_VALUE;
    if (start1 + k / 2 - 1 < nums1.length) mid1 = nums1[start1 + k / 2 - 1];
    if (start2 + k / 2 - 1 < nums2.length) mid2 = nums2[start2 + k / 2 - 1];

    // Throw away half of the array from nums1 or nums2. And cut k in half
    if (mid1 < mid2) {
        return getKth(nums1, start1 + k / 2, nums2, start2, k - k / 2); //nums1.right + nums2
    } else {
        return getKth(nums1, start1, nums2, start2 + k / 2, k - k / 2); //nums1 + nums2.right
    }
}

I 'мы понимаем причину, по которой избавляемся от k / 2 одного массива. Если aMid меньше, чем bMid, то максимальный индекс aMid в смешанном массиве равен k-1, поскольку в B будет вставлено не более k / 2-1 чиселна место перед aMid при их смешивании, так как k / 2-й элемент в B больше, чем aMid.

Пожалуйста, объясните, почему kk / 2 на следующей итерации, так как на 1-й итерации вы удаляете k / 2 записей, которые невозможнобыть k-й записью в объединенном массиве.

Например,

от 0 до k / 2-1 записей в A удалено, потому что aMid меньше, чем bMid, что означает aMid самое большее, чтобы быть (к-1) ая запись.Тем не менее, в массиве B есть еще k / 2 записей, которые нельзя исключать.В следующей итерации функция getkth (A, aStart + k / 2, B, bStart, k - k / 2) bMid = B [0 + k / 4-1], aMid = A [3k / 4-1]. Как насчетлевые записи B [k / 4 to k / 2]?

нет причин исключать их. Каков механизм итерации этого алгоритма?