Divide and Conquer

Divide and conquer

Divide and conquer breaks the original problem into k subproblems and solves them separately. If they remain too large, split them into k smaller subproblems again. Continue recursively until the problems are small enough to solve easily.

Combine the solutions to small problems into solutions to larger ones, working from the bottom up until the original problem is solved.

Four conditions make divide and conquer suitable:

1. The problem becomes easy to solve once its size is sufficiently small.
2. The problem can be divided into smaller problems of the same kind: it has the required substructure.
3. Solutions to the smaller problems can be combined into a solution to the original problem.
4. The subproblems are independent, without shared subproblems. Otherwise, divide and conquer may repeatedly solve the same problems. It can still be used, but dynamic programming is often preferable.

Experience suggests keeping subproblems approximately equal in size. Dividing a problem into k balanced parts is effective; this balancing strategy almost always works better than unequal partitions.

Binary search

A bag contains 16 coins, exactly one of which is counterfeit and lighter than the genuine coins. Find it using an instrument that compares two groups of coins, reporting whether their weights are equal and which group is lighter.

Split the 16 coins equally into A and B. Weigh A against B. If A is lighter, solve the subproblem in A; otherwise, solve the subproblem in B.

Each iteration of binary search halves the remaining array. In the worst case there are $O(\log n)$ iterations, with $O(1)$ work inside each iteration. The total worst-case time complexity is therefore $O(\log n)$.