Divide and Conquer

There are three types of divide and conquer problems. The first type of problem mainly focuses on binary search aspect of divide and conquer. The second type of problems focuses on different types of sorting algorithms and how they can be incorporated into divide and conquer questions. The third type of problems is generalizied divide and conquer problem. We will discuss each one of these seperately in the coming tutorials.

The main idea of divide and conquer problem is splitting the main problem into two smaller components, assume that each one of the components have already been solved recursively and then try to solve the bigger problem using the solution of the two smaller components. For example, merge sort is a perfect case of a divide and conquer problem.

In merge sort, we first divide the array given into two components, the first half and the second half. After dividing them into these two components, we then recursively apply merge sort algorithm on each of these components and assume they are already sorted. Now the problem becomes given two sorted arrays, how do we merge them into one sorted array. We can use a pointer on each of these sorted arrays to solve the last part of the problem.

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade