Divide and Conquer

Split, solve, combine

Divide and conquer is a recipe with three steps. Divide: break the input into two or more smaller subproblems of the same kind. Conquer: solve each subproblem recursively (the base case handles the smallest pieces). Combine: stitch the sub-answers into the answer for the whole.

1. Divide — cut the problem into smaller subproblems of the same shape (often two halves).
2. Conquer — solve each subproblem by recursion; the base case answers the smallest pieces directly.
3. Combine — assemble the sub-answers into the full answer (sometimes this is the hard part, sometimes free).

Binary search is divide and conquer

You already saw binary search in the foundations rung. It's the simplest divide-and-conquer: look at the middle of a sorted array, then throw away half and recurse on the other half. Here divide is "pick the middle," conquer is "search one side," and combine is trivial — the side you recursed into holds the answer.

// search target in sorted a[lo..hi]; returns index or -1
int bsearch(const int a[], int lo, int hi, int target) {
    if (lo > hi) return -1;              // base case: empty range
    int mid = lo + (hi - lo) / 2;        // divide
    if (a[mid] == target) return mid;
    if (a[mid] < target)
        return bsearch(a, mid + 1, hi, target);   // conquer right half
    else
        return bsearch(a, lo, mid - 1, target);   // conquer left half
}

Merge sort previews the pattern

Sorting is the headline example. Merge sort divides an array into two halves, sorts each half recursively, then *merges* the two sorted halves into one. Unlike binary search, the combine step does real work — that merge is where the magic lives. You'll build it in full next guide; here just see the shape.

[ 5  2  8  1 ]            <- divide
   /        \
[ 5  2 ]   [ 8  1 ]       <- divide again
  / \        / \
[5] [2]    [8] [1]        <- base case: length-1 is sorted
  \ /        \ /
[ 2  5 ]   [ 1  8 ]       <- combine (merge)
      \      /
   [ 1  2  5  8 ]         <- final merge

A length-1 array is already sorted — that's the base case. Everything else is divide (split in half) and combine (merge). Hold onto this shape; the full code lives in the next guide, and the same skeleton reappears in quicksort with a different divide step.

Why it produces recurrences

Because a divide-and-conquer algorithm describes its own cost in terms of smaller copies of itself, its running time is naturally written as a recurrence relation — an equation where T(n) refers to T(of something smaller).

1. Binary search: T(n) = T(n/2) + O(1) — one half, constant combine. Solves to O(log n).
2. Merge sort: T(n) = 2T(n/2) + O(n) — two halves, linear merge. Solves to O(n log n).
3. The pattern T(n) = aT(n/b) + work covers most divide-and-conquer costs; a later rung's Master Theorem solves it on sight.