Find Maximum and minimum in an array by comparing in pairs

Find the Maximum and minimum of an array using a minimum number of comparisons.

For every problem we will have multiple solutions, everyone can have their own solution.

For this problem here we have three approaches to solve this problem - 


  1. First Approach "Simple Linear Search"
  2. Second Approach "Tournament Method (Divide and Conquer)"
  3. The third Approach "Compare in Pairs"


Description -  

If n is odd then initialize min and max as the first element. 

If n is even then initialize min and max as minimum and maximum of the first two elements respectively. 

For the rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively. 

********Code********

package javaoneworld.learndsa.problems;


public class JavaOneWorldDSA {
    /* Class Pair is used to return two values from getMinMax() */
    static class Pair {

        int min;
        int max;
    }



    static Pair getMinMax(int arr[], int n) {
        Pair minmax = new Pair();
        int i;
        /* If array has even number of elements then 
    initialize the first two elements as minimum and 
    maximum */
        if (n % 2 == 0) {
            if (arr[0] > arr[1]) {
                minmax.max = arr[0];
                minmax.min = arr[1];
            } else {
                minmax.min = arr[0];
                minmax.max = arr[1];
            }
            i = 2;
            /* set the starting index for loop */
        } /* If array has odd number of elements then 
    initialize the first element as minimum and 
    maximum */ else {
            minmax.min = arr[0];
            minmax.max = arr[0];
            i = 1;
            /* set the starting index for loop */
        }
 
        /* In the while loop, pick elements in pair and 
     compare the pair with max and min so far */
        while (i < n - 1) {
            if (arr[i] > arr[i + 1]) {
                if (arr[i] > minmax.max) {
                    minmax.max = arr[i];
                }
                if (arr[i + 1] < minmax.min) {
                    minmax.min = arr[i + 1];
                }
            } else {
                if (arr[i + 1] > minmax.max) {
                    minmax.max = arr[i + 1];
                }
                if (arr[i] < minmax.min) {
                    minmax.min = arr[i];
                }
            }
            i += 2;
            /* Increment the index by 2 as two 
               elements are processed in loop */
        }

        return minmax;
    }

    /* Testing the implemented program  */
    public static void main(String args[]) {
        int arr[] = {999, 98, 986, 56, 550, 7986};
        int arr_size = 6;
        Pair minmax = getMinMax(arr, arr_size);
        System.out.println("Minimum element is :"+ minmax.min);
        System.out.println("Maximum element is :"+ minmax.max);

    }

}
   
Time Complexity: O(n)

Total number of comparisons: Different for even and odd n


1 comment:

  1. Here’s what that could mean for a city outlined by its fanaticism. If you, like me, are of the thoughts that possibly this presumably be} a enjoyable factor to attempt, it’s a good idea to set some personal guardrails for yourself. For example, I never put down greater than $15 on any particular person wager 바카라사이트 outcome of|as a result of} I didn’t need to lose greater than price of|the price of} an inexpensive meal. Derevensky was also fast to level out that the most important driver of this new legality isn’t particular person habit, but quite revenue potential at the government degree. You depend on Marketplace to break down the world’s occasions and let you know the way it} impacts you in a fact-based, approachable way. We depend on your financial help to maintain making that potential.

    ReplyDelete