Coders Packet

Finding Minimum and Maximum elements in an Array using DAC algorithm in JAVA

By Shiroli Nigam

Implement a program to find Minimum and Maximum elements in an Array using the Divide and Conquer paradigm in java.

Divide and Conquer Paradigm

In this blog, we will implement a JAVA program to find maximum and minimum elements in an array using Divide and Conquer paradigm.

This is an algorithm design paradigm. In this type of algorithm, a problem is broken down into two or more sub-problems of the same or related type until they become simple enough to be solved directly. Then those solutions of sub-problems are combined which makes the solution of an original problem.

The divide-and-conquer paradigm is often used to find an optimal solution to a problem. For example, to sort a given list of n natural numbers, split it into two lists of about n/2 numbers each, sort each of them in turn, and interleave both results appropriately to obtain the sorted version of the given list. This type of approach is known as the merge sort algorithm. 

Logic

For the given array we will divide the array till the sub-array is of the size one or two, after that we will compare the elements to find the minimum and maximum elements in the sub-array. By using the bottom-up approach we will merge the sub-array until the final minimum and maximum elements are found. 

Code

public class Solution {
    public static int[] recMinMax(int[] arr, int start, int end) {
        if(start >= end) {
            return new int[]{arr[start], arr[start]};
        }
        int[] m = new int[2];
        int[] m1 = recMinMax(arr, start, start + (end-start)/2);
        int[] m2 = recMinMax(arr, start + (end-start)/2+1, end);
        m[0] = Math.min(m1[0],m2[0]);
        m[1] = Math.max(m1[1],m2[1]);
        return m;
    }
    public static void main(String[] args) {
        int a[] = {5,8,15,12,4,10,9,6};
        int ans[] = recMinMax(a, 0, 7);
        System.out.println("Min : " + ans[0]);
        System.out.println("Max : " + ans[1]);
    }
}

Output

Min : 4
Max : 15

Download project

Reviews Report

Submitted by Shiroli Nigam (shirolinigam)

Download packets of source code on Coders Packet