Implementing MinMax Algorithm in Java

Finding the minimum and maximum elements in a dataset is a common problem in computer science. While you can solve this using simple iteration, using a divide-and-conquer approach is more efficient in certain scenarios, especially in recursive algorithms. In this blog post, we’ll explore a recursive Java implementation of the Min-Max algorithm.

What is the Min-Max Algorithm?

The Min-Max algorithm splits the array into smaller parts, recursively determines the minimum and maximum of each part, and then combines the results. This divide-and-conquer approach reduces the number of comparisons compared to a naive linear method.

Why Use Divide-and-Conquer?

It minimizes the number of comparisons.
More efficient for large datasets.
Demonstrates recursion and good problem-solving strategies.

Java Code:

import java.io.*;

public class MinMax {

    static int mid;

    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // Read number of elements
        System.out.println("Enter the number of elements: ");
        int n = Integer.parseInt(reader.readLine());
        int[] a = new int[n];

        // Read each element into the array
        for (int i = 0; i < n; i++) {
            System.out.println("Enter element " + (i + 1) + ": ");
            a[i] = Integer.parseInt(reader.readLine());
        }

        // Call the recursive min-max function
        int[] result = Minmax(a, 0, n - 1);

        // Display the result
        System.out.println("\nMinimum = " + result[0] + "\nMaximum = " + result[1]);
    }

    // Recursive function to find min and max
    public static int[] Minmax(int[] a, int low, int high) {
        int[] result = new int[2]; // result[0] = min, result[1] = max

        // Base case: Only one element
        if (low == high) {
            result[0] = a[low];
            result[1] = a[low];
        }
        // Base case: Only two elements
        else if (high - low == 1) {
            if (a[high] < a[low]) {
                result[0] = a[high];
                result[1] = a[low];
            } else {
                result[0] = a[low];
                result[1] = a[high];
            }
        }
        // Recursive case: More than two elements
        else {
            mid = (low + high) / 2;
            int[] left = Minmax(a, low, mid);      // Min and Max from left half
            int[] right = Minmax(a, mid + 1, high); // Min and Max from right half

            result[0] = Min(left[0], right[0]); // Overall min
            result[1] = Max(left[1], right[1]); // Overall max
        }

        return result;
    }

    // Utility method to find minimum of two numbers
    public static int Min(int x1, int x2) {
        return (x1 < x2) ? x1 : x2;
    }

    // Utility method to find maximum of two numbers
    public static int Max(int y1, int y2) {
        return (y1 > y2) ? y1 : y2;
    }
}

How the Code Works

User Input: The user provides the number of elements and inputs them one by one.
Recursive Logic:
- If the subarray has only one element, it’s both the min and max.
- If it has two elements, compare them directly.
- If it has more than two elements, the array is split into halves and the function is called recursively.
The results from left and right halves are merged by comparing their mins and maxes.

Sample Input/Output

Enter the number of elements:
5
Enter element 1:
0
Enter element 2:
1
Enter element 3:
2
Enter element 4:
3
Enter element 5:
5

Minimum = 0
Maximum = 5

Output Explanation

Given the array [0, 1, 2, 3, 5]:

The array is recursively divided:
- First into [0, 1, 2] and [3, 5]
- Then [0, 1] and [2], and so on
The base cases (with one or two elements) are directly compared.
The final results are merged:
- Min of all segments: 0
- Max of all segments: 5

Hence, the program correctly returns:

Minimum = 0
Maximum = 5

@ankurm