DSA Interview Prep · Урок

Медиана двух отсортированных массивов

Решите задачу о медиане двух отсортированных массивов за O(log(min(m,n))), применяя двоичный поиск по границе разбиения более короткого массива

«Медиана двух отсортированных массивов» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Медиана двух отсортированных массивов

Медиана двух отсортированных массивов (LeetCode 4) — классическая сложная задача. Даны два отсортированных массива nums1 (длина m) и nums2 (длина n); найдите медиану их объединённой отсортированной последовательности за O(log(min(m,n))) времени. Наивный подход объединяет оба массива за O(m+n), но оптимальное решение использует двоичный поиск по границам разбиения. Это одна из самых часто задаваемых сложных задач в ведущих технологических компаниях.

# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0

nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5

print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))

Наивный подход со слиянием

Простейший подход за O(m+n): объедините оба отсортированных массива, затем найдите медиану. Слияние двух отсортированных массивов занимает O(m+n). Медиана массива длины L равна arr[L//2], если L нечётно, или (arr[L//2-1] + arr[L//2]) / 2, если L чётно. Это решение корректно, но не соответствует требованию O(log(min(m,n))). На собеседовании всегда сначала представляйте этот подход, чтобы обозначить базовый вариант, а затем переходите к оптимальному решению.

def find_median_naive(nums1, nums2):
    # Merge two sorted arrays
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i]); i += 1
        else:
            merged.append(nums2[j]); j += 1
    merged += nums1[i:] + nums2[j:]
    L = len(merged)
    if L % 2 == 1:
        return float(merged[L // 2])
    return (merged[L//2 - 1] + merged[L//2]) / 2.0

print(find_median_naive([1,3],[2]))    # 2.0
print(find_median_naive([1,2],[3,4]))  # 2.5

Идея разбиения

Ключевая идея: медиана разделяет объединённый массив на две равные части. Нужно найти разбиение nums1 и разбиение nums2, такие что: (1) общие размеры левых частей и правых частей совпадают; (2) все элементы в левых частях ≤ всех элементов в правых частях. Если выполнить двоичный поиск правой точки разбиения в nums1, разбиение в nums2 автоматически определяется ограничением на общую длину.

# Partition concept visualised:
# nums1: [1, 3] | [5, 7]   (partition after index 1)
# nums2: [2, 4] | [6, 8]   (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5

nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])

Двоичный поиск границы разбиения

Выполняйте двоичный поиск по индексу разбиения i в nums1 — более коротком массиве. Индекс разбиения j в nums2 определяется как j = (m+n+1)//2 - i, благодаря чему в левых частях оказывается (m+n+1)//2 элементов. Разбиение корректно, если nums1[i-1] ≤ nums2[j] и nums2[j-1] ≤ nums1[i]. Двоичный поиск изменяет i в большую или меньшую сторону, пока это равновесие не будет найдено.

def find_median_sorted_arrays(nums1, nums2):
    # Ensure nums1 is the shorter array
    if len(nums1) > len(nums2):
        return find_median_sorted_arrays(nums2, nums1)
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # partition index in nums1
        j = (m + n + 1) // 2 - i  # partition index in nums2
        # Boundary values with sentinels
        max_left1  = float('-inf') if i == 0 else nums1[i-1]
        min_right1 = float('inf')  if i == m else nums1[i]
        max_left2  = float('-inf') if j == 0 else nums2[j-1]
        min_right2 = float('inf')  if j == n else nums2[j]
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            # Found the correct partition
            if (m + n) % 2 == 1:
                return float(max(max_left1, max_left2))
            return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
        elif max_left1 > min_right2:
            hi = i - 1  # i is too large, move left
        else:
            lo = i + 1  # i is too small, move right
    return 0.0

print(find_median_sorted_arrays([1,3],[2]))     # 2.0
print(find_median_sorted_arrays([1,2],[3,4]))   # 2.5

Трассировка двоичного поиска

Проследим работу на примере nums1=[1,3], nums2=[2]: m=2, n=1, total=3, lo=0, hi=2. i=(0+2)//2=1, j=(2+1+1)//2-1=1. max_left1=nums1[0]=1, min_right1=nums1[1]=3, max_left2=nums2[0]=2, min_right2=inf (j=1=n). Проверка: 1≤inf и 2≤3 ✓. Общая длина нечётная: возвращаем max(1,2)=2.0. ✓ Алгоритм нашёл разбиение на первом шаге, поскольку размеры массивов невелики.

def find_median_traced(nums1, nums2):
    if len(nums1) > len(nums2):
        return find_median_traced(nums2, nums1)
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    step = 0
    while lo <= hi:
        step += 1
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        ml1 = float('-inf') if i==0 else nums1[i-1]
        mr1 = float('inf')  if i==m else nums1[i]
        ml2 = float('-inf') if j==0 else nums2[j-1]
        mr2 = float('inf')  if j==n else nums2[j]
        print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1
    return 0.0

print(find_median_traced([1,3],[2]))

Почему поиск выполняется по короткому массиву

Двоичный поиск выполняется по короткому массиву, чтобы получить сложность O(log(min(m,n))) вместо O(log(m+n)). Разбиение длинного массива полностью определяется разбиением короткого. Обмен входных массивов, если len(nums1) > len(nums2), гарантирует, что короткий массив всегда будет пространством поиска. Инвариант таков: когда j выводится из i и общей длины, j всегда является допустимым индексом разбиения для nums2.

# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)

m, n = 3, 5  # m <= n
half = (m+n+1)//2
for i in range(m+1):
    j = half - i
    valid = 0 <= j <= n
    print(f'i={i}: j={j}, valid={valid}')

Обработка чётной и нечётной общей длины

Если объединённая длина нечётная, медиана равна максимуму левых частей (max(max_left1, max_left2)). Если длина чётная, медиана равна среднему арифметическому максимума левых частей и минимума правых частей. Формула (m+n+1)//2 для размера левой части работает в обоих случаях: при чётной общей длине она даёт n//2 с одним дополнительным элементом слева, и для получения чётной медианы мы усредняем результат с min_right.

def median_demo(a, b):
    merged = sorted(a + b)
    L = len(merged)
    expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
    computed = find_median_sorted_arrays(a[:], b[:])
    print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
    assert abs(expected - computed) < 1e-9

def find_median_sorted_arrays(nums1, nums2):
    if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
    m,n=len(nums1),len(nums2); lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2; j=(m+n+1)//2-i
        ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
        ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1
    return 0.0

median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[])  # single array

Крайние случаи

Критически важные крайние случаи: (1) один массив пуст — медианой будет медиана непустого массива; (2) все элементы одного массива меньше элементов другого — разбиение окажется у одного из краёв; (3) повторяющиеся элементы — алгоритм обрабатывает их естественным образом; (4) оба массива имеют длину 1 — простая медиана двух элементов. Всегда проверяйте эти случаи после написания решения. Сентинел-значения -∞ и +∞ позволяют корректно обрабатывать граничные разбиения (i=0 или i=m).

def fmsa(a,b):
    if len(a)>len(b): return fmsa(b,a)
    m,n=len(a),len(b); lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2; j=(m+n+1)//2-i
        ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
        ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1

# Edge cases
print(fmsa([], [1]))             # 1.0
print(fmsa([2], []))             # 2.0
print(fmsa([1,2], [3,4]))        # 2.5
print(fmsa([3,4], [1,2]))        # 2.5
print(fmsa([1,1,1], [1,1]))      # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35]))  # 17.5

Обобщение: k-й наименьший элемент в двух массивах

Задача о медиане обобщается до поиска k-го наименьшего элемента среди двух отсортированных массивов. На каждом шаге сравнивайте k//2-й элемент каждого массива. Отбрасывайте меньшую половину: все эти k//2 элементов меньше k-го элемента, поэтому их можно удалить из рассмотрения. Уменьшите k на k//2 и продолжите поиск рекурсивно. Базовые случаи: один массив пуст (верните k-й элемент оставшегося массива) или k=1 (верните минимум из первых элементов обоих массивов). Время: O(log k) = O(log(m+n)).

def kth_smallest(nums1, nums2, k):
    if not nums1: return nums2[k-1]
    if not nums2: return nums1[k-1]
    if k == 1: return min(nums1[0], nums2[0])
    # Compare k//2-th elements
    half = k // 2
    i = min(half, len(nums1)) - 1  # index in nums1
    j = min(half, len(nums2)) - 1  # index in nums2
    if nums1[i] <= nums2[j]:
        # Eliminate first (i+1) elements of nums1
        return kth_smallest(nums1[i+1:], nums2, k - (i+1))
    else:
        return kth_smallest(nums1, nums2[j+1:], k - (j+1))

nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
    print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')

Сравнение всех подходов

Итоговое сравнение: Объединение массивов: время O(m+n), память O(m+n). Двоичный поиск по разбиению: время O(log(min(m,n))), память O(1). Рекурсивный поиск k-го наименьшего элемента: время O(log(m+n)), стек вызовов O(log k). Метод двоичного поиска по разбиению — именно тот, который ожидают увидеть интервьюеры при решении этой задачи. Это самая сложная распространённая задача LeetCode для понятного объяснения — отрабатывайте логику разбиения и четыре проверки границ, пока не будете выполнять их автоматически.

# Performance comparison
import time, random

def merge_median(a, b):
    merged = sorted(a+b)
    L=len(merged)
    return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2

def binary_median(a, b):
    if len(a)>len(b): return binary_median(b,a)
    m,n=len(a),len(b);lo,hi=0,m
    while lo<=hi:
        i=(lo+hi)//2;j=(m+n+1)//2-i
        ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
        ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
        if ml1<=mr2 and ml2<=mr1:
            if (m+n)%2==1: return float(max(ml1,ml2))
            return (max(ml1,ml2)+min(mr1,mr2))/2.0
        elif ml1>mr2: hi=i-1
        else: lo=i+1

for size in [100, 10000]:
    a = sorted(random.sample(range(size*2), size))
    b = sorted(random.sample(range(size*2), size))
    t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
    t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
    print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')

Стратегия общения на собеседовании

Для этой сложной задачи на собеседовании: (1) Сразу назовите наивный подход слияния за O(m+n) — это покажет вашу компетентность. (2) Объясните цель O(log(min(m,n))) и идею разбиения. (3) Разберите инвариант разбиения: максимум слева для первого массива ≤ минимум справа для второго массива и максимум слева для второго массива ≤ минимум справа для первого массива. (4) Явно обработайте сторожевые значения. (5) Назовите формулу медианы для массивов нечётной и чётной длины. (6) Проверьте решение на 1–2 примерах. Такая структура демонстрирует системный подход к решению задач даже в случае задачи, которую мало кто из кандидатов способен идеально решить под давлением.

# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        return findMedianSortedArrays(nums2, nums1)
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        max_l1 = nums1[i-1] if i > 0 else float('-inf')
        min_r1 = nums1[i]   if i < m else float('inf')
        max_l2 = nums2[j-1] if j > 0 else float('-inf')
        min_r2 = nums2[j]   if j < n else float('inf')
        if max_l1 <= min_r2 and max_l2 <= min_r1:
            if (m + n) % 2:
                return float(max(max_l1, max_l2))
            return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
        elif max_l1 > min_r2: hi = i - 1
        else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2]))    # 2.0
print(findMedianSortedArrays([1,2],[3,4]))  # 2.5

Быстрая проверка

Проверьте своё понимание понятий из курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию», рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы узнали, что медиану двух отсортированных массивов можно найти за O(log(min(m,n))) с помощью двоичного поиска правильной границы разбиения в более коротком массиве, разбиение корректно, когда максимум слева для первого массива ≤ минимум справа для второго массива и максимум слева для второго массива ≤ минимум справа для первого массива, а сторожевые значения обрабатывают граничные случаи, а обобщение для k-го наименьшего элемента использует рекурсивный подход с поэтапным исключением половин за O(log k). Поздравляем с завершением уроков по разделу «Разделяй и властвуй» — теперь у Вас есть комплексный набор инструментов для собеседований по программированию!

Часто задаваемые вопросы

Урок «Медиана двух отсортированных массивов» бесплатный?

Да — полный текст урока «Медиана двух отсортированных массивов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Медиана двух отсортированных массивов»?

Решите задачу о медиане двух отсортированных массивов за O(log(min(m,n))), применяя двоичный поиск по границе разбиения более короткого массива Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Медиана двух отсортированных массивов»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Шаблон «Разделяй и властвуй»
Подсчёт инверсий с помощью изменённой сортировки слиянием
Элемент большинства: голосование Бойера—Мура
Медиана двух отсортированных массивов

← Назад к DSA Interview Prep