0Pricing
Coding Interview Prep · Lektion

Divide-and-Conquer-Vorlage

Leiten Sie aus Merge Sort die dreistufige Vorlage (Teilen, Lösen, Zusammenführen) ab und wenden Sie sie systematisch auf neue Problemformen an.

Divide-and-Conquer-Vorlage ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was ist Divide and Conquer?

Divide and Conquer (D&C) löst ein Problem, indem es dieses in unabhängige Teilprobleme desselben Typs aufteilt, jedes davon rekursiv löst und die Lösungen anschließend kombiniert. Das entscheidende Wort ist unabhängig — Teilprobleme teilen keinen Zustand, anders als bei DP, wo sie sich überlappen. Klassische Beispiele sind Mergesort, binäre Suche, Quicksort, Closest Pair of Points und schnelle Matrixmultiplikation. D&C erreicht durch dieses dreistufige Schema typischerweise eine Laufzeit von O(n log n).

# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP:  sub-problems OVERLAP (same sub-problem solved multiple times)

# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing

# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n)  [merge sort]
# T(n) = T(n/2) + O(1) → O(log n)     [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]

Das dreistufige Schema

Jeder D&C-Algorithmus folgt drei Schritten: (1) Teilen — Teilen Sie das Problem in zwei oder mehr kleinere Teilprobleme auf, typischerweise am Mittelpunkt. (2) Lösen — Lösen Sie jedes Teilproblem rekursiv. Definieren Sie einen Basisfall, der die Rekursion beendet (üblicherweise n ≤ 1). (3) Kombinieren — Führen Sie die Lösungen der Teilprobleme zu einer Gesamtlösung zusammen. Die eigentliche Kreativität liegt vollständig im Schritt des Kombinierens; das Teilen besteht normalerweise lediglich darin, am Mittelpunkt aufzuteilen.

def divide_and_conquer(arr, lo, hi):
    # BASE CASE: trivial sub-problem
    if lo >= hi:
        return base_case_result(arr, lo, hi)
    
    # DIVIDE: split at midpoint
    mid = (lo + hi) // 2
    
    # CONQUER: solve sub-problems recursively
    left_result  = divide_and_conquer(arr, lo, mid)
    right_result = divide_and_conquer(arr, mid + 1, hi)
    
    # COMBINE: merge results
    return combine(left_result, right_result, arr, lo, mid, hi)

def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)

Mergesort als kanonisches Beispiel

Mergesort veranschaulicht D&C perfekt: Teilen Sie das Array am Mittelpunkt. Lösen Sie das Problem, indem Sie jede Hälfte rekursiv sortieren. Kombinieren Sie die beiden sortierten Hälften, indem Sie sie in O(n) zusammenführen. Der Zusammenführungsschritt enthält die gesamte Arbeit. Rekurrenz: T(n) = 2T(n/2) + O(n). Nach dem Master-Theorem gilt in Fall 2: T(n) = O(n log n). Dies ist die wichtigste D&C-Rekurrenz, die Sie auswendig können sollten.

def merge_sort(arr):
    # BASE CASE
    if len(arr) <= 1:
        return arr
    # DIVIDE
    mid = len(arr) // 2
    # CONQUER
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # COMBINE
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

print(merge_sort([5, 3, 8, 1, 9, 2]))  # [1,2,3,5,8,9]

Kurzübersicht zum Master-Theorem

Das Master-Theorem löst Rekurrenzen der Form T(n) = aT(n/b) + f(n): Fall 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Fall 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Fall 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Mergesort: a=2, b=2, f(n)=O(n), n^log_2(2)=n → Fall 2 → O(n log n).

# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n)    → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1)    → a=2,b=2,f=1,n^1=n >> 1  → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2)  → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1)     → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree

recurrences = [
    ('Merge sort: 2T(n/2)+n', 'O(n log n)'),
    ('Binary search: T(n/2)+1', 'O(log n)'),
    ('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
    ('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)

Maximum Subarray: D&C-Ansatz

Der D&C-Ansatz für Maximum Subarray: Die Lösung liegt entweder vollständig in der linken Hälfte, vollständig in der rechten Hälfte oder überquert den Mittelpunkt. Für den dritten Fall erweitern Sie den Bereich von mid aus nach links und von mid+1 aus nach rechts. Dabei bestimmen Sie in jeder Richtung die maximale Summe und kombinieren anschließend beide Ergebnisse. Dieser D&C-Ansatz mit O(n log n) ist langsamer als Kadane's O(n), veranschaulicht das Schema jedoch sehr anschaulich und ist eine häufige Interviewfrage zu D&C.

def max_subarray_dc(nums, lo=None, hi=None):
    if lo is None: lo, hi = 0, len(nums) - 1
    if lo == hi: return nums[lo]
    mid = (lo + hi) // 2
    # Conquer
    left_max  = max_subarray_dc(nums, lo, mid)
    right_max = max_subarray_dc(nums, mid + 1, hi)
    # Cross-midpoint sum
    left_sum = curr = 0
    for i in range(mid, lo - 1, -1):
        curr += nums[i]
        left_sum = max(left_sum, curr)
    right_sum = curr = 0
    for i in range(mid + 1, hi + 1):
        curr += nums[i]
        right_sum = max(right_sum, curr)
    cross_max = left_sum + right_sum
    return max(left_max, right_max, cross_max)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums))  # 6

Potenzfunktion: schnelles Potenzieren

Fast Power (LeetCode 50): Berechnen Sie x^n in O(log n) mithilfe von D&C. Wenn n gerade ist: x^n = (x^(n/2))^2. Wenn n ungerade ist: x^n = x × x^(n-1). Behandeln Sie negative n mit x^(-n) = 1/x^n. Jeder rekursive Aufruf halbiert n, daher beträgt die Rekursionstiefe O(log n). Dies ist ein klares Beispiel dafür, dass der Kombinationsschritt lediglich aus einer Multiplikation bestehen kann — trivial, aber effektiv.

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    # BASE CASE
    if n == 0: return 1
    # DIVIDE and CONQUER
    half = my_pow(x, n // 2)
    if n % 2 == 0:
        return half * half          # even: x^n = (x^(n/2))^2
    else:
        return x * half * half      # odd: x^n = x * (x^(n/2))^2

print(my_pow(2, 10))   # 1024
print(my_pow(2, -2))   # 0.25
print(my_pow(3, 5))    # 243
print(my_pow(0, 0))    # 1

Sorted Array to BST

Convert Sorted Array to BST (LeetCode 108) verwendet D&C: Wählen Sie den Mittelpunkt als Wurzel, um eine ausgewogene Höhe sicherzustellen, und erstellen Sie den linken Teilbaum rekursiv aus der linken Hälfte sowie den rechten Teilbaum aus der rechten Hälfte. Dadurch entsteht ein höhenbalancierter BST mit minimaler Höhe O(log n). Die D&C-Struktur entspricht der binären Suche — auf jeder Rekursionsebene wird der Mittelpunkt als Wurzel des aktuellen Teilbereichs festgelegt.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums):
    def helper(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])    # DIVIDE at midpoint
        node.left  = helper(lo, mid - 1)  # CONQUER left
        node.right = helper(mid + 1, hi)  # CONQUER right
        # COMBINE: already done by assignment
        return node
    return helper(0, len(nums) - 1)

def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root))  # [-10,-3,0,5,9] (sorted, proving BST property)

Wann D&C nicht die beste Wahl ist

D&C verursacht einen gewissen Aufwand: die Tiefe des Aufrufstacks, das Ausschneiden von Arrays (wenn keine Indizes verwendet werden) und der Kombinationsschritt. D&C ist optimal, wenn der Kombinationsschritt O(n) oder schneller ist. Wenn sich Teilprobleme überlappen, berechnet D&C Lösungen unnötigerweise mehrfach — dann wird DP benötigt. Wenn der Kombinationsschritt dominiert (z. B. mit O(n²)), verbessert D&C naive Ansätze nicht. Sie sollten wissen, wann welche Methode geeignet ist: D&C für unabhängige Teilprobleme, DP für sich überlappende Teilprobleme.

# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead

def fib_dc(n):
    if n <= 1: return n
    return fib_dc(n-1) + fib_dc(n-2)  # O(2^n)!

def fib_dp(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a+b
    return a  # O(n)

print(fib_dp(30))  # fast
# fib_dc(40) would take seconds — do not run large values!

D&C für die binäre Suche in einer sortierten Matrix

Eine Suche in einer 2D-Matrix (LeetCode 240), in der jede Zeile und jede Spalte sortiert ist, kann mit D&C gelöst werden: Beginnen Sie in der oberen rechten Ecke. Wenn current > target ist, gehen Sie nach links und schließen die Spalte aus. Wenn current < target ist, gehen Sie nach unten und schließen die Zeile aus. Wenn beide Werte gleich sind, wurde das Ziel gefunden. Dieser Algorithmus mit O(m+n) ist technisch gesehen kein rekursives D&C, verwendet aber dieselbe zentrale Idee: In jedem Schritt wird die Hälfte des Suchraums ausgeschlossen.

def search_matrix(matrix, target):
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # start top-right
    while row < m and col >= 0:
        val = matrix[row][col]
        if val == target:
            return True
        elif val > target:
            col -= 1  # eliminate this column
        else:
            row += 1  # eliminate this row
    return False

matrix = [
    [1,   4,  7, 11, 15],
    [2,   5,  8, 12, 19],
    [3,   6,  9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5))   # True
print(search_matrix(matrix, 20))  # False

Analyse des Rekursionsbaums

Verwenden Sie für D&C-Rekurrenzen, die nicht zum Master-Theorem passen, die Methode des Rekursionsbaums. Zeichnen Sie jede Ebene der rekursiven Aufrufe und addieren Sie den Arbeitsaufwand pro Ebene. Bei Mergesort gibt es auf Ebene k 2^k Teilprobleme der Größe n/2^k. Arbeit pro Ebene = 2^k × O(n/2^k) = O(n). Die Gesamtzahl der Ebenen beträgt log n. Gesamtaufwand = O(n log n). Diese visuelle Methode funktioniert für jede Rekurrenz und vermittelt ein intuitives Verständnis dafür, warum D&C normalerweise O(n log n) erreicht.

# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)

import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')

Kommunikation im Vorstellungsgespräch zu D&C

Wenn Sie in einem Vorstellungsgespräch eine D&C-Lösung präsentieren: (1) Nennen Sie die drei Schritte ausdrücklich: 'Ich teile am Mittelpunkt, löse jede Hälfte rekursiv und kombiniere sie anschließend durch Zusammenführen.' (2) Erklären Sie den Basisfall klar. (3) Leiten Sie die Rekurrenz her: T(n) = 2T(n/2) + O(n). (4) Wenden Sie das Master-Theorem oder den Rekursionsbaum an, um O(n log n) herzuleiten. (5) Erwähnen Sie, wann D&C besser oder schlechter als Alternativen ist (DP bei überlappenden Teilproblemen, Kadane's bei Maximum Subarray).

# D&C interview template to memorize:
def dc_template(problem, lo, hi):
    # 1. BASE CASE (state it first)
    if lo == hi: return solve_base(problem, lo)
    # 2. DIVIDE
    mid = (lo + hi) // 2
    # 3. CONQUER
    left  = dc_template(problem, lo, mid)
    right = dc_template(problem, mid + 1, hi)
    # 4. COMBINE (this is where the algorithm-specific logic goes)
    return combine_results(left, right, problem, lo, mid, hi)

def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)

print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')

Schnelltest

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep, die in dieser Lektion behandelt wurden.

Zusammenfassung der Lektion

In dieser Lektion haben Sie Folgendes gelernt: Divide and Conquer folgt dem Schema: Basisfall → am Mittelpunkt teilen → rekursiv lösen → kombinieren, T(n) = 2T(n/2) + O(n) ergibt nach Fall 2 des Master-Theorems O(n log n), und D&C ist optimal für unabhängige Teilprobleme, während bei überlappenden Teilproblemen DP benötigt wird. Als Nächstes wenden wir D&C an, um Inversionen in einem Array mithilfe eines modifizierten Mergesorts zu zählen.

Häufig gestellte Fragen

Ist die Lektion „Divide-and-Conquer-Vorlage“ kostenlos?

Ja — der vollständige Text von „Divide-and-Conquer-Vorlage“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Divide-and-Conquer-Vorlage“?

Leiten Sie aus Merge Sort die dreistufige Vorlage (Teilen, Lösen, Zusammenführen) ab und wenden Sie sie systematisch auf neue Problemformen an. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um Coding Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Divide-and-Conquer-Vorlage“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Divide-and-Conquer-Vorlage
  2. Inversionen mit modifiziertem Merge Sort zählen
  3. Majority Element: Boyer-Moore-Abstimmung
  4. Median zweier sortierter Arrays
← Zurück zu Coding Interview Prep