Divide and Conquer Algorithm Design
by Piyush Wadhawan
Divide and rule also known as Divide and Conquer is a strategy that many generals used in the past centuries and is in fact still used to this very day.
Many empires were built thanks to this strategy. To divide a strong power into smaller weaker sections and take care of them separately. Today, this strategy is not only used by the military but also in programming. In fact, you might also be using it daily in the form of some software with an algorithm based on this concept.
In this blog we will discuss the Divide and Conquer algorithm.
What is Divide and Conquer algorithm?
As discussed above, Divide and Conquer is an algorithm which works by dividing a problem into smaller section and then solving it individually.
Why is it used?
During battles and wars Divide and Conquer was used because it caused less casualties, took less time and it was a way by which a large army could be defeated by less power. In short it was an efficient approach. For this same reason it is used today in programming. Efficiency is something that is of utmost importance while coding. By efficiency I mean the speed of your code, space-time complexity, power consumed and so on.
The main concepts:
1. Divide: To split the problem into smaller components.
2. Conquer: To solve the smaller components.
Use of divide and Conquer in programming
The most common use that is learnt by every coder at a very early stage in his/her programming journey is to find a specific number in a sorted array of size N.
The most common and obvious solution is (Linear Search) to use a loop to iterate through the array, comparing every element with the number that is being searched.
___________________________________________________________________
Code: Linear search
int main()
{
int a[] = {1,2,3,4,5,6,7,8,9,10};
int s;
cin>>s;
for(int i = 0; i < N; i++)
if(a[i] == s)
{
cout<<”Element fount”;
break;
}
}
___________________________________________________________________
Time Complexity:
Best case:
O(N) = 1
The element we are looking for is located at index 0 so the loop runs only once.
Worst case:
O(N) = N
The element we are looking for is located at the end of the array so the loop will run N number of times.
___________________________________________________________________
Now let’s try to improve the time complexity by using Binary search which uses the concept of Divide and Conquer to increase the efficiency of the code.
Binary Search
In binary search we repeatedly divide the search interval into half each iteration. Binary search is an algorithm that can work as a searching algorithm only if the array is sorted. In this method we first take two variables (F, L) and assign the values of the first index and the last index to them. Then we find the index number of the middle element (M = (F + L)/2) then we compare the element present at position M with the element that we are searching for (S).
We check the following conditions:
1. a[M] == S
2. a[M] > S
3. a[M] < S
1. If the first condition is satisfied we print the element at the middle position and break from the loop.
2. If the second condition is satisfied then we change the value of the ending limit to M-1 and repeat the process again.
3. If the third condition is satisfied then we change the value of the starting limit to M+1 and repeat the process again.
We keep repeating this process till we find the element and if the element is not there then the loop runs for a fixed period which is logN after which the loop ends. The loop will continue to run till the index of the last element in the search interval is greater than or equal to the first element in that particular search interval.
This is the general working of this algorithm. We can also use recursive calls to create this algorithm. Here we will see the both codes for recursive method.
___________________________________________________________________
Code: Binary Search
___________________________________________________________________
1.While loop method
int Binary_Search(int Arr[], int F, int L, int S)
{
while(R >= L)
{
int M = F + (L — l) / 2;
// If the element is present at the middle index position
if (Arr[M] == S)
return M;
// If element is smaller than mid, then
// Then S can only be present in left section of the array
else if (Arr[M] > S)
L = M — 1
// Else the element can only be present
// in right subarray
else
F = M + 1;
}
// We reach here when element is not present in array
return -1;
}
___________________________________________________________________
2.Reccurrsive method
int Binary_Search(int Arr[], int F, int L, int S)
{
if (R >= L)
{
int M = F + (L — l) / 2;
// If the element is present at the middle index position
if (Arr[M] == S)
return M;
// If element is smaller than mid, then
// Then S can only be present in left section of the array
else if (Arr[M] > S)
return Binary_Search(Arr, F, M — 1, S); //Recursive call
// Else the element can only be present
// in right subarray
else
return Binary_Search(Arr, M + 1, L, S); //Recursive call
}
// We reach here when element is not present in array
return -1;
}
___________________________________________________________________
Time Complexity
The recurrence relation for this code is: T(n) = T(n/2) + O(1)
Best case:
O(N) = 1
The element that we are searching for is present at the middle index position
Worst case:
O(N) = logN
This happens when we keep dividing the array till the last possible division.
Note: There is no difference in the value of Time complexity between the two different ways of writing the code.
___________________________________________________________________
As seen from the above discussion we can solve solve the searching problem using Divide and Conquer technique more efficiently than running a single loop and iterating through the entire array. Binary search was just one application of this technique. There are plenty of other algorithms out there which use the same technique some of which are:
§ Merge Sort
§ Quicksort
§ Strassen’s Algorithm
§ Closest Pair Points
__________________________Happy Learning__________________________
