Divide And Conquer 🌎

Photo by Hassan Pasha on Unsplash

In general, a divide and conquer strategy is a technique in which a given task is broken down into sub-tasks making it easier to complete them individually. This strategy has been in use since time immemorial in warfare tactics, politics,etc to efficiently deal with a given problem. It has been evolving and has been adapted in various aspects of our life to make our tasks easier.

This article will be a very beginner-friendly to help you properly understand the concept. So, if you have very little to no experience with Divide and Conquer algorithm or programming in general, don’t worry! I will be covering the topic from the very basic in an easily understandable approach.

DIVIDE AND CONQUER ALGORITHM

In Computer Science, a divide and conquer is a type of algorithm designed to break down a problem into sub-problems which are usually simple enough to be solved directly. These solution to sub-problems can be combined to give our final answer.

The Divide and Conquer technique can be understood as three parts :

1. Divide —Dividing the problem into sub-problems
2. Conquer — Conquering the sub-problems by solving them recursively.
3. Combine — Combining all the solutions to sub-problems and merging them into solution of our original problem.

Any solution to an Divide and Conquer algorithm will look like this —

Photo by Khan Academy

Now, let’s not get overwhelmed by the above diagram. In practice, once you understand the concept and practice a few problems which use this algorithm, constructing a mind-map like above will be a no-brainer! So, lets see a few common applications which use Divide and Conquer algorithm.

MERGE SORT

This is a classical problem which uses Divide and Conquer technique to solve the task effectively. We are given an array of elements which we are required to sort in ascending or descending order according to the given condition.

Using the most naive approach possible would be to find all the permutations of the array and see if its sorted. Well, the time complexity of this approach would be O(N*N!) since it would involve finding all the N! permutations of array and N iterations to check if they are sorted. Well…this approach is right away discarded 🚮.

Using a slightly better approach, we can sort the array by taking each element into account and placing them at their proper places. This would still take a time complexity of O(N²) which is very inefficient for large arrays. Lets see the optimized approach using Merge Sort.

Merge Sort — divide, sort, merge by GeeksforGeeks

• We begin by dividing the given array into smaller parts and convert the problem into sub-problems of sorting the sub-arrays.
• Recurse until we reach array whose size is equal to 1. At this point, the merging process will begin as shown in the diagram.
• We merge two sub-arrays until we get the array of original size. The merging process will be handled by a merge function which will merge two sub-arrays in linear time.

//We pass array A, its leftmost index l and rightmost index r 
mergeSort(A, l, r):
    if l> r :          //We have completed dividing into sub-arrays
        return
    mid= (l+r)/2          //Each time, find the mid-point to divide
    mergeSort(A, l, mid)  //recursively divide first sub-array
    mergeSort(A, mid+1, r)//recursively divide second sub-array
    merge(A, l, mid, r)   //merge all the sub-arrays in a sorted way

Now, the main task would be to merge the divide array in an efficient manner. The merge function would look as follows -

merge(A, l, mid, r):
    p1=0,p2=0,i=0   // maintain two pointers, one for each sub-array and another for maintaining index of array below
    temp = []       // an empty array which will hold sorted array
// Inserting elements according to their value 
    while p1 <=mid and p2 <=r:
        if A[p1]<A[p2]:
            temp[i++] = A[p1++]
        else :
            temp[i++] = A[p2++]
//add remaining elements
    while p1 <= mid :
        temp[i++] = A[p1++]
    while p2 <= r :
        temp[i++] = A[p2++]
//copy temp to A[l...r]
    for i=l to r :
        A[i] = temp[i-l]

The above pseudocode might look a bit complex( and confusing🤕), but just understand what we are doing at the basic level and implementation would be easy. We are maintaining two pointers and inserting the elements into auxiliary array(temp) in a sorted manner by picking one element each time from A[l…mid] and A[mid…r]. At last, we copy the auxiliary array back to A[l…r] and now our range l…r is sorted !

The time complexity of this approach is O(NlogN) which is a lot better than O(N²) required for the naive approach. We require O(N) time complexity for merging process and there are a total of logN steps at max that we need to perform to fully sort the array.

I would recommend using an sorting visualizer to get a better understanding of how sorting works step-by-step. One merge sort visualizer that I found helpful —Merge sort Visualizer

BINARY SEARCH 🔍

This is yet another classical problem which uses Divide and Conquer algorithm to solve a given task. This problem would clearly make you understand how the Divide and Conquer algorithm really works and emphasize its importance to you.

Lets consider a game. I will be choosing a random number and your task will be to guess and find the number I have chosen. You will only be given hint about if the chosen number is smaller or larger than your guess(Don’t worry, I won’t cheat😇). How many guess at max do you think, you will need? The number I choose could be anywhere from one to a one billion(1,000,000,000) 🤯. Think on it for a minute before moving on…

Well, if you are thinking this to be like searching for a needle in a haystack, you are mistaken (and congrats! if you did find the answer). The naive approach will be to guess one number after the other which could take upto a billion guesses(That would really get boring !) .The Divide and conquer will be a powerful tool at your disposal to solve this problem a lot quicker. The answer to above problem using this approach would be -

ANSWER : 30

Linear vs Binary search

Shocked?! Let’s see the logic behind how we are able to correctly find the number I chose within 30 guess.

• We will start by choosing the mid-point of my given range — (1 + 1000000000)/2 = 50,00,00,000 (rounded down).
• Then, you would be given the hint about whether my chosen number is greater or less than your guess. Using this hint, we can completely eliminate half of our search space and continue our search only in the other half.
• We will do this every time and continue halving our search space until we eventually land on the correct guess.

NOTE :Keep in mind though, that this approach only works when our range is sorted.

The max number of guess you would require to find an element using this approach is Log2(N) . Following is the pseudocode for this problem -

//key is the element to be searched
binarySearch(arr, key, low, high)//our function to search for 
    if low > high :              //our base condition
        return False 
    else :
        mid = (low + high) / 2   // halving the search space each time
        if key == arr[mid]  :    // found the required key
            return mid
        else if key < data[mid] :// key is sure to be on the right 
            return binarySearch(arr, key, mid + 1, high)
        else :                   // key is now surely on the left 
            return binarySearch(arr, key, low, mid - 1)

✍ SUMMARY

Divide and Conquer is one of simplest algorithmic techniques but one which makes our tasks much more efficient and fast. We saw how we can simplify our search to just 30 steps instead of a billion! This technique is employed in many other problems such as —

• Quick Sort
• Fast Exponentiation
• Strassen’s Algorithm
• Kasturba Algorithm
• Closest Pair of Points

Whenever we identify any problem in which we can decompose the given problem into simpler sub-problem, we must look if we can apply this technique to make our tasks simpler. Most of the implementations would be simple. We just need to reason & identify whether a particular problem can be solved using this approach.

This is one of most easy way to optimize our algorithms and make our programs faster. Hopefully, this article can help you get started with using this algorithmic technique to simplify your work and make your programs blazing fast!👨‍💻