Problem Solving

Divide and Conquer

Students divide a large puzzle into smaller groups and fit them together.

Divide and Conquer definition

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those, and using their results.

In Spanish
divide y vencerás
Topic
Algorithms and problem-solving

Divide and Conquer in a picture

Divide and Conquer diagramTo find a list’s largest value, find the largest value in each half, then compare those two results.Divide the list into two halvesMake smaller versions of the same problemFind each half’s maximumSolve the subproblemsTake the larger resultCombine the two answers
To find a list’s largest value, find the largest value in each half, then compare those two results.

How it works

A small enough subproblem is handled directly. For larger inputs, divide them into smaller parts and apply the same strategy. Some methods combine all partial results, while a search can discard parts that cannot contain the answer.

Worked examples

What is a natural base case for finding a maximum in a nonempty list?

A list with one item, whose maximum is that item.

How does binary search use divide and conquer?

It splits the possible range and solves only the half that can contain the target.

How can a recursive sorting method combine two sorted halves?

Merge them by repeatedly taking the smaller front item.

Common mistake

Make the subproblems smaller and explain how their solutions produce a solution to the original problem.

Quick check

What comes after solving the subproblems when both results are needed?

Why include a base case?

Show answer

It tells you when to stop dividing and solve directly.

Can two subproblems have different sizes?

Show answer

Yes, the sizes depend on the method.

Sources

Flashcard

Divide and Conquer

Reveal the definition

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those, and using their results.

Effortless Math. “Divide and Conquer.” Math Dictionary.