Медиана алгоритма двух отсортированных массивов для O(log(m+n))

Как уже упоминалось, цель алгоритма — найти медиану двух отсортированных массивов. Связанное решение достигает этого, выполняя Двоичный поиск, где ключевая идея состоит в том, чтобы рекурсивно сузить пространство поиска, отбрасывая примерно половину элементов из массивов на каждом этапе, тем самым достигая логарифмической временной сложности. Поскольку оба массива отсортированы, а k — это расширенный индекс того, где была бы медиана, если бы два массива были объединены, мы используем логику двоичного поиска, чтобы найти медиану без фактического объединения массивов.

Функция solve определена для выполнения двоичного поиска. Он принимает параметры k, aStart, aEnd, bStart и bEnd, которые представляют целевой индекс и текущие границы поиска в массивах A и B. Фрагмент, на который вы ссылаетесь,

if (aEnd < aStart) {
    return B[k - aStart];
}
if (bEnd < bStart) {
    return A[k - bStart];
}

Это базовый случай, обрабатывающий сценарий, когда сегмент одного массива исчерпан. Если мы исчерпаем сегмент массива A, мы фактически сведем задачу к поиску (k - aStart)-го элемента в массиве B, поскольку все значения в A были учтены.

• k представляет k-ю позицию, которую мы ищем в объединенных отсортированных массивах.
• Если все элементы от A до aStart учтены, эти элементы уже вносят вклад в k.
• Новая k-я позиция относительно B должна учитывать количество уже рассмотренных элементов из A, следовательно, k - aStart.

Например, предположим, что у нас есть два отсортированных массива A и B:

A = [1, 3, 8, 15]
B = [7, 11, 18, 19, 21]

Мы пытаемся найти медиану объединенных отсортированных массивов. Объединенный массив будет:

[1, 3, 7, 8, 11, 15, 18, 19, 21]

Индекс медианы объединенного массива равен k = floor(9 / 2) = 4, что соответствует значению 11.

Алгоритм рекурсивно сужает пространство поиска. Вы можете самостоятельно отслеживать переменные по рекурсивным вызовам, но в конечном итоге сегмент A исчерпывается, aEnd < aStart, то есть все элементы в A были учтены. Когда выбран базовый случай, aStart = 3 и aEnd = 2. Поэтому, функция возвращает

B[k - aStart] = B[4 - 3] = B[1] = 11

что правильно.

Опять же, мы вычитаем aStart из k, так как это сужает позицию k, чтобы отразить оставшиеся элементы в B, учитывая количество элементов, уже учтенных в A. Эта настройка гарантирует, что даже когда один сегмент исчерпан, алгоритм по-прежнему правильно идентифицирует k-й элемент в другом массиве.

Эта логика применяется аналогичным образом, когда сегмент массива B исчерпан. Уменьшая k на aStart или bStart, мы корректно подстраиваемся под уже рассмотренные элементы и продолжаем поиск в оставшемся сегменте массива.

Возврат B[k - (aStart + bStart)] приведет к неправильному индексированию B. Помните, k — это индекс медианы в объединенных массивах. Когда один массив исчерпан, медиана лежит в другом, поэтому k следует корректировать только на количество рассматриваемых элементов из исчерпанного массива. Вычитание aStart + bStart из k приведет к неправильной индексации в неисчерпанном массиве.