Examples of Divide and Conquer Algorithm

Characteristics of Divide and Conquer Algorithm:

Complexity Analysis of Divide and Conquer Algorithm:

1. Finding the maximum element in the array:

We can use Divide and Conquer Algorithm to find the maximum element in the array by dividing the array into two equal sized subarrays, finding the maximum of those two individual halves by again dividing them into two smaller halves. This is done till we reach subarrays of size 1. After reaching the elements, we return the maximum element and combine the subarrays by returning the maximum in each subarray.

C++

// function to find the maximum no.
// in a given array.
int findMax(int a[], int lo, int hi)
{
    // If lo becomes greater than hi, then return minimum
    // integer possible
    if (lo > hi)
        return INT_MIN;
    // If the subarray has only one element, return the
    // element
    if (lo == hi)
        return a[lo];
    int mid = (lo + hi) / 2;
    // Get the maximum element from the left half
    int leftMax = findMax(a, lo, mid);
    // Get the maximum element from the right half
    int rightMax = findMax(a, mid + 1, hi);
    // Return the maximum element from the left and right
    // half
    return max(leftMax, rightMax);
}

Java

// Function to find the maximum number
// in a given array.
static int findMax(int[] a, int lo, int hi)
{
    // If lo becomes greater than hi, then return
    // minimum integer possible
    if (lo > hi)
        return Integer.MIN_VALUE;
    // If the subarray has only one element, return the
    // element
    if (lo == hi)
        return a[lo];
    int mid = (lo + hi) / 2;
    // Get the maximum element from the left half
    int leftMax = findMax(a, lo, mid);
    // Get the maximum element from the right half
    int rightMax = findMax(a, mid + 1, hi);
    // Return the maximum element from the left and
    // right half
    return Math.max(leftMax, rightMax);
}

Python3

# Function to find the maximum number
# in a given array.
def find_max(a, lo, hi):
    # If lo becomes greater than hi, then return minimum
    # integer possible
    if lo > hi:
        return float('-inf')
    # If the subarray has only one element, return the
    # element
    if lo == hi:
        return a[lo]
    mid = (lo + hi) // 2
    # Get the maximum element from the left half
    left_max = find_max(a, lo, mid)
    # Get the maximum element from the right half
    right_max = find_max(a, mid + 1, hi)
    # Return the maximum element from the left and right
    # half
    return max(left_max, right_max)

// Function to find the maximum number
// in a given array.
static int FindMax(int[] a, int lo, int hi)
{
    // If lo becomes greater than hi, then return
    // minimum integer possible
    if (lo > hi)
        return int.MinValue;
    // If the subarray has only one element, return the
    // element
    if (lo == hi)
        return a[lo];
    int mid = (lo + hi) / 2;
    // Get the maximum element from the left half
    int leftMax = FindMax(a, lo, mid);
    // Get the maximum element from the right half
    int rightMax = FindMax(a, mid + 1, hi);
    // Return the maximum element from the left and
    // right half
    return Math.Max(leftMax, rightMax);
}

JavaScript

// Function to find the maximum number
// in a given array.
function findMax(a, lo, hi) {
    // If lo becomes greater than hi, then return minimum
    // integer possible
    if (lo > hi)
        return Number.MIN_VALUE;
    // If the subarray has only one element, return the
    // element
    if (lo === hi)
        return a[lo];
    const mid = Math.floor((lo + hi) / 2);
    // Get the maximum element from the left half
    const leftMax = findMax(a, lo, mid);
    // Get the maximum element from the right half
    const rightMax = findMax(a, mid + 1, hi);
    // Return the maximum element from the left and right
    // half
    return Math.max(leftMax, rightMax);
}

2. Finding the minimum element in the array:

Similarly, we can use Divide and Conquer Algorithm to find the minimum element in the array by dividing the array into two equal sized subarrays, finding the minimum of those two individual halves by again dividing them into two smaller halves. This is done till we reach subarrays of size 1. After reaching the elements, we return the minimum element and combine the subarrays by returning the minimum in each subarray.

3. Merge Sort:

We can use Divide and Conquer Algorithm to sort the array in ascending or descending order by dividing the array into smaller subarrays, sorting the smaller subarrays and then merging the sorted arrays to sort the original array.

Introduction to Divide and Conquer Algorithm – Data Structure and Algorithm Tutorials

Divide and Conquer Algorithm is a problem-solving technique used to solve problems by dividing the main problem into subproblems, solving them individually and then merging them to find solution to the original problem. In this article, we are going to discuss how Divide and Conquer Algorithm is helpful and how we can use it to solve problems.

Table of Content

Divide and Conquer Algorithm Definition
Working of Divide and Conquer Algorithm
Characteristics of Divide and Conquer Algorithm
Examples of Divide and Conquer Algorithm
Complexity Analysis of Divide and Conquer Algorithm
Applications of Divide and Conquer Algorithm
Advantages of Divide and Conquer Algorithm
Disadvantages of Divide and Conquer Algorithm

Examples of Divide and Conquer Algorithm

1. Finding the maximum element in the array:

2. Finding the minimum element in the array:

3. Merge Sort:

Introduction to Divide and Conquer Algorithm – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us