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...