Voorbereiding op programmeerinterviews · Les

Mediaan van twee gesorteerde arrays

Los median-of-two-sorted-arrays op in O(log(min(m,n))) met binary search op de scheidingsgrens van de kortste array.

Les 4 van 413 stappen

Mediaan van twee gesorteerde arrays is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.

De mediaan van twee gesorteerde arrays

Mediaan van twee gesorteerde arrays (LeetCode 4) is een klassiek moeilijk probleem. Gegeven twee gesorteerde arrays nums1 (lengte m) en nums2 (lengte n), vind je de mediaan van hun gecombineerde gesorteerde reeks in O(log(min(m,n)))-tijd. Een naïeve aanpak voegt beide arrays samen in O(m+n), maar de optimale oplossing gebruikt binair zoeken naar partitiegrenzen. Dit is een van de moeilijkste problemen die het vaakst wordt gevraagd bij toonaangevende technologiebedrijven.

# 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))

Naïeve aanpak met samenvoegen

De eenvoudigste aanpak in O(m+n): voeg beide gesorteerde arrays samen en zoek daarna de mediaan. Twee gesorteerde arrays samenvoegen kost O(m+n). De mediaan van een array met lengte L is arr[L//2] als L oneven is, of (arr[L//2-1] + arr[L//2]) / 2 als L even is. Dit is correct, maar voldoet niet aan het vereiste O(log(min(m,n))). Presenteer deze aanpak altijd eerst in een sollicitatiegesprek om een basisoplossing vast te leggen en optimaliseer daarna.

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

Het partitie-idee

Het belangrijkste inzicht: de mediaan verdeelt de gecombineerde array in twee even grote helften. We moeten een partitie van nums1 en een partitie van nums2 vinden waarvoor geldt: (1) de linkerhelften hebben dezelfde totale grootte als de rechterhelften. (2) Alle elementen in de linkerhelften zijn ≤ alle elementen in de rechterhelften. Als we met binair zoeken het juiste partitiepunt in nums1 vinden, wordt de partitie in nums2 automatisch bepaald door de beperking op de totale lengte.

# 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])

Binair zoeken naar de partitie

Zoek binair naar de partitie-index i van nums1 (de kortere array). De partitie-index j in nums2 wordt bepaald als j = (m+n+1)//2 - i (zodat de linkerhelften (m+n+1)//2 elementen bevatten). De partitie is geldig wanneer nums1[i-1] ≤ nums2[j] en nums2[j-1] ≤ nums1[i]. Pas i omhoog of omlaag aan met binair zoeken om dit evenwicht te vinden.

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

De binaire zoekopdracht doorlopen

Doorloop 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). Controleer: 1≤inf en 2≤3 ✓. Totaal is oneven: return max(1,2)=2.0. ✓ Het algoritme vond de partitie in de eerste stap omdat de arraygroottes klein zijn.

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]))

Waarom binair zoeken in de kortste array

We zoeken binair in de kortste array om O(log(min(m,n))) te bereiken in plaats van O(log(m+n)). De partitie van de langste array wordt volledig bepaald door de partitie van de kortste array. Door de invoer om te wisselen als len(nums1) > len(nums2), is de kortste array altijd de zoekruimte. De invariant is: wanneer j wordt afgeleid van i en de totale lengte, is j altijd een geldige partitie-index voor 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}')

Omgaan met even en oneven totale lengtes

Wanneer de gecombineerde lengte oneven is: de mediaan is het maximum van de linkerhelften (max(max_left1, max_left2)). Wanneer de lengte even is: de mediaan is het gemiddelde van het maximum van de linkerhelften en het minimum van de rechterhelften. De formule (m+n+1)//2 voor de grootte van de linkerhelft werkt voor beide gevallen: bij een even totaal levert deze n//2 op (één extra element links), en we nemen het gemiddelde met min_right om de mediaan voor een even lengte te krijgen.

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

Randgevallen

Belangrijke randgevallen: (1) Eén array is leeg — de mediaan van de niet-lege array. (2) Alle elementen van de ene array zijn kleiner dan die van de andere — de partitie ligt aan een uiterste kant. (3) Dubbele elementen — het algoritme verwerkt deze vanzelf. (4) Beide arrays hebben lengte 1 — een eenvoudige mediaan van twee elementen. Test deze gevallen altijd nadat je de code hebt geschreven. Met de wachtwaarden -∞ en +∞ kun je partities aan de grenzen (i=0 of i=m) netjes verwerken.

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

Generalisatie: het k-de kleinste element in twee arrays

Het mediaanprobleem kan worden veralgemeend naar het vinden van het k-de kleinste element in twee gesorteerde arrays. Vergelijk bij elke stap het k//2-de element van beide arrays. Verwijder de kleinere helft: die k//2 elementen zijn allemaal kleiner dan het k-de element, dus je kunt ze weggooien. Verlaag k met k//2 en ga recursief verder. Basisgevallen: één array is leeg (geef het k-de element van de overgebleven array terug), of k=1 (geef het minimum van de eerste elementen terug). Tijd: 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)}')

Alle aanpakken vergelijken

Laatste vergelijking: Arrays samenvoegen: O(m+n) tijd, O(m+n) ruimte. Binair zoeken naar de partitie: O(log(min(m,n))) tijd, O(1) ruimte. Recursie voor het k-de kleinste element: O(log(m+n)) tijd, O(log k) aanroepstack. De methode met binair zoeken naar de partitie is wat interviewers bij dit probleem verwachten. Dit is het moeilijkste veelvoorkomende LeetCode-probleem om duidelijk uit te leggen — oefen de partitielogica en de vier grenscontroles totdat ze automatisch gaan.

# 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')

Strategie voor communicatie tijdens sollicitatiegesprekken

Voor dit moeilijke probleem tijdens een sollicitatiegesprek: (1) Noem meteen de naïeve aanpak waarbij je in O(m+n) samenvoegt — daarmee laat je zien dat je de basis beheerst. (2) Leg het doel van O(log(min(m,n))) en het idee van de partitie uit. (3) Loop de invariant van de partitie door: max_left1 ≤ min_right2 en max_left2 ≤ min_right1. (4) Behandel schildwachten expliciet. (5) Noem de mediaanformule voor een oneven en even aantal elementen. (6) Test met één of twee voorbeelden. Dit raamwerk in vijf stappen laat zien dat je problemen systematisch oplost, zelfs bij een probleem dat maar weinig kandidaten onder druk perfect oplossen.

# 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

Korte controle

Test je begrip van de concepten uit deze les van Data Structures & Algorithms — Coding Interview Prep.

Beantwoord dit in de interactieve les

Samenvatting van de les

In deze les leerde je: de mediaan van twee gesorteerde arrays kan worden gevonden in O(log(min(m,n))) door binair te zoeken naar de juiste grens van de partitie in de kortere array, de partitie geldig is wanneer max_left1 ≤ min_right2 en max_left2 ≤ min_right1, waarbij schildwachtwaarden grensgevallen afhandelen, en de generalisatie naar het k-de kleinste element een recursieve aanpak met halvering gebruikt in O(log k) tijd. Gefeliciteerd met het voltooien van de lessen over verdeel en heers — je hebt nu een uitgebreide gereedschapskist voor technische sollicitatiegesprekken!

Gratis beginnen

Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis

Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.

Cursussen: 90
Lessen: 360

Gratis beginnen met leren Bekijk de volledige cursus

Veelgestelde vragen

Is de les “Mediaan van twee gesorteerde arrays” gratis?

Ja — de volledige tekst van “Mediaan van twee gesorteerde arrays” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.

Wat leer ik in “Mediaan van twee gesorteerde arrays”?

Los median-of-two-sorted-arrays op in O(log(min(m,n))) met binary search op de scheidingsgrens van de kortste array. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.

Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?

Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.

Hoe lang duurt de les “Mediaan van twee gesorteerde arrays”?

De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.

Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?

Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.

Alle lessen in deze cursus

Divide-and-conquer-sjabloon
Inversies tellen met aangepaste merge sort
Meerderheidselement: Boyer-Moore-stemmen
Mediaan van twee gesorteerde arrays

← Terug naar Voorbereiding op programmeerinterviews