CODEWITHSUNDEEP
algorithmminmax
Ymi
Ymi

Reputation: 768

Algorithm to find minimum AND maximum of an unsorted array

First I would like to preface this by saying this is not a coding question, but an algorithm question. Given an unsorted array, how can we efficiently find the minimum and maximum items inside? Many examples exist finding either max or mininum but I'm interested in finding both at once. A simple iterative comparison approach would not be efficent, and here is my attempt, visually with an example and also via pseudocode:

Visual Example

public static int[] findMinMax(int array[], int n, int m){
        int temp, mid;
        int[] left = new int[2]; // initialize new arrays with size 2 to store left and right side minmax values
        int[] right = new int[2];
        if (n <= m){ // Only 1 item is left in array
            int[] tempStorage = {array[n], array[n]};
            return tempStorage;
        }
        else if (n+1 == m){ // Only two items are in the array
            if (array[n] > array[m]){ // swap values if left value is bigger than right value
                temp = array[m];
                array[m] = array[n];
                array[n] = temp;
            }
        }
        mid = (n+m)/2; // find index of the midpoint in the array
        // Split the array into two recursively:
        left = findMinMax(array, n, mid);
        right = findMinMax(array, mid+1, m);

        //Compare the minimum values for left and right arrays, then assign the min to the first item in array
        if (left[n] < right[mid+1]){
            array[n] = left[n];
        }
        else{
            array[n] = right[mid+1];
        }
        //Compare the maximum values for left and right arrays, then assign the max to last item in array
        if (left[mid] > right[m]){
            array[m] = left[mid];
        }
        else{
            array[m] = right[m];
        }

    System.out.printf("Min: %d\nMax: %d\n", array[n], array[m]);
        return array;

So I attempt to split the array into two until only pairs are left; I then compare them and rearrange the pair such that the minimum is on the left, and max on the right. Subsequently, we move back up and compare only the minimum and maximum for the left and right partial array. At the end of the algorithm, the first value in the array should be the minimum and the last value should be the maximum. We don't really care about anything else in between.

I'm not sure about the time complexity, but I think it should be O(n/2)? Is there any other way to do this with an efficient time complexity? I would also like to know some feedback on the algorithm I presented. Thank you.

Upvotes: 0

Views: 1035

Answers (1)

Y.T.
Y.T.

Reputation: 2739

Finding max/min in an array cannot be done in fewer than n - 1 comparisons, it is very clear why - you need to compare every element.

If you take a look at your algorithm, it in fact takes more than n - 1 comparisons, just count the number of red numbers appeared. But each red number actually corresponds to more than 1 comparison.

Upvotes: 1

Related Questions