In Chapter 13, Sorting and Searching Algorithms, we learned how to develop the merge and quick sort algorithms. What both sorting solutions have in common is that they are divide and conquer algorithms. Divide and conquer is one of the approaches to algorithm design. It breaks the problem into small subproblems that are similar to the original problem, it solves the subproblems recursively, and combines the solutions of the subproblems to solve the original problem.
The divide and conquer algorithm can be split into three parts:
- Divide the original problem into smaller subproblems (smaller instances of the original problem).
- Conquer the smaller subproblems by solving them with recursive algorithms that return the solution for the subproblems. The base case of the recursive algorithm solves and returns the solution for the smallest subproblem.
- Combine the solutions of the subproblems into the solution for the original problem.
As we have already covered the two most famous divide...