DAA 13_max_min_dnc Divide & Conquer

Max & Min using Divide & Conquer — Interactive

Divide & Conquer splits the array, solves small parts, then merges results with only 2 comparisons per merge. Compare it with a naive scan (about 2(n−1) comparisons).

Visualizer

Step: 0 / 0

Array (comma-separated)

Auto-play speed (ms)

Show recursion stack Show mid marker Show merge comparisons

Legend Active Range L-half R-half mid MIN MAX

Comparisons: 0

Current Range

—

mid

—

Best MIN so far

—

Best MAX so far

—

Message

Enter an array and click Start.

Call Stack (Top = Latest) Depth: 0

Base cases: size 1 → 0 comparisons, size 2 → 1 comparison. Merge step → 2 comparisons (min + max).

Live Pseudocode

The highlighted line matches the current visualization step.

MaxMin(A, l, r):
  if l == r:
    return (A[l], A[l])
  if r == l + 1:
    if A[l] < A[r]:
      return (A[l], A[r])
    else:
      return (A[r], A[l])
  mid = ⌊(l + r)/2⌋
  (min1, max1) = MaxMin(A, l, mid)
  (min2, max2) = MaxMin(A, mid+1, r)
  return ( min(min1, min2), max(max1, max2) )

Tip: Watch how ranges shrink to size 1 or 2 (base cases), then merge back up.

DnC vs Naive (Comparisons)

Comparison Counter

DnC (this run): 0

Naive scan: 0 (≈ 2(n−1))

—

Complexity (Quick Visual)

Choose n (array size)

n = 8

Estimated comparisons

Naive ≈ 14 comparisons

DnC ≈ 10 comparisons (about 3n/2 − 2)

Meaning: DnC reduces comparisons by doing fewer “max checks” and fewer “min checks” overall.