1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to find min and max of 100 numbers ?

  1. Dec 14, 2014 #1
    1. The problem statement, all variables and given/known data
    The minimum number of comparisons required to find the minimum and the maximum of 100
    numbers is ...........

    2. Relevant equations
    ##T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2##

    3. The attempt at a solution
    Recurrence for the above problem is
    ##T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2 \approx 1.5 \times n - 2##

    hence ##T(100)=1.5 \times 100 - 2 = 148##
    But by solving like this I'm coming up with the ans 162

    We can divide list of 100 numbers in two list (50,50). Now upon combining the result of these two list 2 more comparisons will be required. Now recursively we break the lists like below, which will make a binary tree

    ##100 \implies (50,50)##
    ##50 \implies (25,25)##
    ##25 \implies (12,13)##
    ##12 \implies (6,6), 13 \implies (6,7)##
    ##6 \implies (3,3), 7 \implies(3,4)##
    ##3 \implies (2,1), 4 \implies (2,2)##

    By combining the results upwards in the tree with 2 comparisons on merging each two lists I'm coming up with ans 162 what am I overcounting.
     
  2. jcsd
  3. Dec 14, 2014 #2

    rcgldr

    User Avatar
    Homework Helper

    Splitting up the lists as you've shown, I also get 162. You can either split up the lists into powers of two, or use an iterative approach for 148 compares. In this case, it should be easy to see why the number of compares is ⌈(3n/2)⌉ - 2: the first pair takes 1 compare, all of the remaining pairs take 3 compares, and if there are a odd number of elements, the last one takes 2 compares.

    Code (Text):

    static size_t cmp;              // number of compares

    MINMAX findminmax(int a[], size_t sizea)
    {
    MINMAX minmax;
    size_t i;
    int min;
    int max;

        if(sizea == 0){             // if empty array
            minmax.min = 0;         //   set min = max = 0
            minmax.max = 0;
            return minmax;
        }
        if(sizea == 1){             // if size == 1
            minmax.min = a[0];      //   set min = max = a[0]
            minmax.max = a[0];
            return minmax;
        }
        if(a[0] <= a[1]){           // set initial min and max
            minmax.min = a[0];
            minmax.max = a[1];
        } else {
            minmax.min = a[1];
            minmax.max = a[0];
        }
        cmp += 1;
        for(i = 2; i < (sizea-1); i += 2){ // find min and max
            if(a[i] <= a[i+1]){
                if(a[i  ] < minmax.min)
                    minmax.min = a[i  ];
                if(a[i+1] > minmax.max)
                    minmax.max = a[i+1];
            } else {
                if(a[i  ] > minmax.max)
                    minmax.max = a[i  ];
                if(a[i+1] < minmax.min)
                    minmax.min = a[i+1];
            }
            cmp += 3;
        }
        if(i < sizea){
            if(a[i] < minmax.min)
                minmax.min = a[i];
            if(a[i] > minmax.max)
                minmax.max = a[i];
            cmp += 2;
        }
        return minmax;
    }
     
     
    Last edited: Dec 15, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to find min and max of 100 numbers ?
  1. Max and min (Replies: 9)

  2. Find V max, V min (Replies: 6)

Loading...