# Divide and Conquer

Introduction to Divide and Conquer With Binary Search - Algorithms for Coding Interviews in Python

DAA Divide and Conquer Introduction - javatpoint

In divide and conquer approach, a problem is divided into smaller problems, then the smaller problems are solved independently, and finally the solutions of smaller problems are combined into a solution for the large problem.

Divide and conquer is an algorithmic paradigm in which the problem is repeatedly divided into subproblems until we reach a point where each problem is similar and atomic, i.e., can’t be further divided. At this point, we start solving these atomic problems and combining (merging) the solutions.

Generally, divide-and-conquer algorithms have three parts:

**Divide the problem**into a number of sub-problems that are smaller instances of the same problem.**Conquer the sub-problems**by solving them recursively. If they are small enough, solve the sub-problems as base cases.**Combine the solutions**to the sub-problems into the solution for the original problem.

Examples

- Binary Search
- Quicksort: It is the most efficient sorting algorithm, which is also known as partition-exchange sort. It starts by selecting a pivot value from an array followed by dividing the rest of the array elements into two sub-arrays. The partition is made by comparing each of the elements with the pivot value. It compares whether the element holds a greater value or lesser value than the pivot and then sort the arrays recursively.
- Merge Sort: It is a sorting algorithm that sorts an array by making comparisons. It starts by dividing an array into sub-array and then recursively sorts each of them. After the sorting is done, it merges them back.
- Tower of Hanoi problem

Find the original version of this page (with additional content) on Notion here.

Created: November 20, 2021 07:19:02