Divide and conquer
One of the important and effective techniques for solving a complex problem is divide and conquer. The divide-and-conquer paradigm divides a problem into smaller sub-problems, and then solves these; finally, it combines the results to obtain a global, optimal solution. More specifically, in divide-and-conquer design, the problem is divided into two smaller sub-problems, with each of them being solved recursively. The partial solutions are merged to obtain a final solution. This is a very common problem-solving technique, and is, arguably, the most commonly used approach in algorithm design.
Some examples of the divide-and-conquer design technique are as follows:
- Binary search
- Merge sort
- Quick sort
- Algorithm for fast multiplication
- Strassen’s matrix multiplication
- Closest pair of points
Let’s have a look at two examples, the binary search and merge sort algorithms, to understand how the divide-and...