Divide & Conquer

Divide & conquer is one of the great problem-solving patterns. The idea is almost lazy: instead of solving a big problem directly, you break it into smaller copies of the same problem, solve each one, and stitch the answers back together. Merge sort, quick sort, and binary search are all built this way. Here we use the simplest possible example — finding the maximum of an array — so the pattern is easy to see.

Intuition

Imagine a single-elimination tournament. You do not rank every player at once — you split them into matches, the winners advance, and at the very top one champion remains. Finding the maximum of an array works the same way: split the array into two halves, find the champion (max) of each half, then the overall champion is just the bigger of those two. The work flows down as you split into smaller and smaller brackets, and the winners flow back up until a single value reaches the top.

Walk through it

On the right, the array [3, 8, 2, 5] starts as the root of a tree. Press Play or step with Next. First comes the divide phase, flowing downward: the root splits into [3, 8] and [2, 5], and each of those splits again until every branch ends in a single element — 3, 8, 2, 5. A single element is the base case: the max of one number is itself.

Then the combine phase flows back upward. Each leaf returns its own value. The left parent takes max(3, 8) = 8; the right parent takes max(2, 5) = 5; and finally the root takes max(8, 5) = 8. That 8 — assembled entirely out of smaller answers — is the maximum of the whole array. The splitting nodes light up on the way down, and the green "winner" values bubble up on the way back.

The code, line by line

def dc_max(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2               # divide
    left = dc_max(arr, lo, mid)        # conquer left half
    right = dc_max(arr, mid + 1, hi)   # conquer right half
    return max(left, right)            # combine

• lo and hi mark the slice we are responsible for (inclusive on both ends). The first call is dc_max(arr, 0, len(arr) - 1).
• Line 2 is the base case: when lo == hi the slice holds exactly one element, and its max is that element (line 3). Recursion must have a base case or it never stops.
• Line 4 is divide: mid is the middle index, splitting the slice into [lo..mid] and [mid+1..hi].
• Lines 5 and 6 are conquer: two recursive calls solve each half independently. Each returns the max of its own slice.
• Line 7 is combine: the answer for the whole slice is simply the larger of the two halves' answers.

The recursion is described by the recurrence T(n) = 2T(n/2) + O(1): each call does O(1) work (one comparison) and makes two calls on halves. By the Master Theorem that solves to O(n) — we still touch every element once, just in a tree-shaped order.

Complexity

The extra space is O(log n) for the call stack — the deepest the recursion goes is the height of the tree. Finding a max does not actually need divide & conquer (a single loop is O(n) and O(1) space), but the shape of this solution is exactly the shape of merge sort and quick sort, where the combine step does real work.

When to use / pitfalls

Practice