Divide and conquer algorithm: Difference between revisions

The Divide and Conquer algorithm (also called the Divide and Conquer method) is a basis for many popular sorting algorithms. An algorithm is simply a series of steps to solve a problem. The general idea of divide and conquer is to take a problem and break it apart into smaller problems that are easier to solve.

This idea can be seen in many popular algorithms. A helpful way to think of this idea, would be when a person looks through a dictionary. For example, if they are looking for the word “Dog”, and land on a page with the word “Firetruck”, the person knows that all the pages to the right of firetruck will not contain dog. They know this because D comes before F in the alphabet. This logic allows a person to spend less time searching, because every time they arrive on a page with the wrong letter, they know that they can ignore the pages to the right or left of that page. This is an example of dividing a problem up into smaller pieces. An algorithm that uses this idea is binary search. For example, to find an item in a sorted list, one would start by looking at the middle item. By comparing the item in the middle to the item one is looking for, one can tell which half of the list the item cannot be in. They only need to look in the other half. One would use this logic again on that half of the list, and so on until there is only one item they need to look at. This way they broke apart the problem of “where in the list is this item” into “which half of the list is this item in” and “where in that half of the list is this item.” Skipping half of the items each time lets them do much less work than looking at every item in the list.