How to find max. and min. in array using minimum comparisons?

Question

This is a interview question: given an array of integers find the max. and min. using minimum comparisons.

Obviously, I can loop over the array twice and use ~2n comparisons in the worst case but I would like to do better.

Well, I can imagine algorithms that need no comparisons at all (e.g. apply counting sort, then pick the first and last item). But I don't suppose that's the point. — , Nov 24 '12 at 19:10
Just out of curiosity, Which companies ask such questions? I have been interviewed by many companies but I have never seen any question like this. — AlienOnEarth, Oct 07 '15 at 07:10
@user395760 Doesn't a counting sort require knowledge about the minimum and maximum value in the array? It seems like you would need to know the range of the numbers in order to initialize the counting array. — DivideByZero, Oct 04 '21 at 16:50

score 82 · Accepted Answer · answered Nov 24 '12 at 19:07

82

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.

answered Nov 24 '12 at 19:07

srbhkmr

2,074
1
14
19

18

Should it not be `3N/2 - 2` since we do not need to update min or max in the very first step? – Phil-ZXX May 09 '15 at 19:22
It takes exactly 3N/2-2 comparisons. – SKR Oct 15 '18 at 06:08

Asiri Rathnayake · Answer 2 · 2012-11-25T00:21:41.297

15

Trying to improve on the answer by srbh.kmr. Say we have the sequence:

A = [a1, a2, a3, a4, a5]

Compare a1 & a2 and calculate min12, max12:

if (a1 > a2)
  min12 = a2
  max12 = a1
else
  min12 = a1
  max12 = a2

Similarly calculate min34, max34. Since a5 is alone, keep it as it is...

Now compare min12 & min34 and calculate min14, similarly calculate max14. Finally compare min14 & a5 to calculate min15. Similarly calculate max15.

Altogether it's only 6 comparisons!

This solution can be extended to an array of arbitrary length. Probably can be implemented by a similar approach to merge-sort (break the array in half and calculate min max for each half).

UPDATE: Here's the recursive code in C:

#include <stdio.h>

void minmax (int* a, int i, int j, int* min, int* max) {
  int lmin, lmax, rmin, rmax, mid;
  if (i == j) {
    *min = a[i];
    *max = a[j];
  } else if (j == i + 1) {
    if (a[i] > a[j]) {
      *min = a[j];
      *max = a[i];
    } else {
      *min = a[i];
      *max = a[j];
    }
  } else {
    mid = (i + j) / 2;
    minmax(a, i, mid, &lmin, &lmax);
    minmax(a, mid + 1, j, &rmin, &rmax);
    *min = (lmin > rmin) ? rmin : lmin;
    *max = (lmax > rmax) ? lmax : rmax;
  }
}

void main () {
  int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11};
  int min, max;
  minmax (a, 0, 9, &min, &max);
  printf ("Min : %d, Max: %d\n", min, max);
}

Now I cannot make out the exact number of comparisons in terms of N (the number of elements in the array). But it's hard to see how one can go below this many comparisons.

UPDATE: We can work out the number of comparisons like below:

At the bottom of this tree of computations, we form pairs of integers from the original array. So we have N / 2 leaf nodes. For each of these leaf nodes we do exactly 1 comparison.

By referring to the properties of a perfect-binary-tree, we have:

leaf nodes (L) = N / 2 // known
total nodes (n) = 2L - 1 = N - 1
internal nodes = n - L = N / 2 - 1

For each internal node we do 2 comparisons. Therefore, we have N - 2 comparisons. Along with the N / 2 comparisons at the leaf nodes, we have (3N / 2) - 2 total comparisons.

So, may be this is the solution srbh.kmr implied in his answer.

edited Nov 25 '12 at 00:21

answered Nov 24 '12 at 22:59

Asiri Rathnayake

1,138
1
11
27

2

It can be implemented with a divide-and-conquer strategy. – Matthew Hall Nov 24 '12 at 23:14
4

+1 Nice analysis. Your _tournament-like_ approach is I think just another way of looking at it. You could do it linearly also, just keep on comparing next 2 unprocessed pairs (a, b) and update the min, max as I explained in my answer. I think in both approaches comparisons made would be `3N/2-2` or `3N/2-3/2` depending on odd/even N. You could save extra recursion space if you go for a linear scan though ;) – srbhkmr Nov 25 '12 at 04:04
5

See Knuth Volume 3, chapter 5.3.3, exercise 16. He says 3N/2 - 2 is the maximum. – WaywiserTundish Nov 25 '12 at 06:51
@srbh.kmr: Indeed, I think the best is approach is to do a linear scan. For some reason it felt like I was "optimizing" on your answer but now it seems it is more of a pessimization... anyway, learned something new :) – Asiri Rathnayake Nov 25 '12 at 16:03
@WaywiserTundish: May be you meant "minimum" instead? May be it was a typo. Cheers! – Asiri Rathnayake Nov 25 '12 at 16:06
3

@AsiriRathnayake: Quoting the referenced exercise: "(I. Pohl.) Show that we can find both the maximum and minimum of a set of n elements, using at most ceiling(3n/2) - 2 comparisons; and the latter number cannot be lowered." – WaywiserTundish Nov 26 '12 at 05:04
@WaywiserTundish: Got it, Cheers! – Asiri Rathnayake Nov 26 '12 at 10:50
Would be glad if someone could elaborate on how to do a "linear scan". – ngmir Oct 25 '17 at 16:47
1

Your analysis assumes a perfect binary tree, however, `n` can be odd or the number of pairs can be odd. With your recursive implementation, this could result in more than `(3n/2)-2` comparisons because you are hitting base cases more often which require extra comparisons. – ngmir Oct 27 '17 at 07:55

saravanan · Answer 3 · 2019-07-19T09:23:06.750

go for divide and conquer !

1,3,2,5

for this finding min,max will take 6 comparisons

but divide them

1,3 ---> will give min 1 and max 3 in one comparison
2,5 ---> will give min 2 and max 5 in one comparison

now we can compare two mins and maxs

min(1,2) --> will give the final min as 1 (one comparison)
max(3,5) ---> will give the final max as 5 (one comparison)

so totally four comparisons to find both min and max.

score 5 · Answer 4 · answered Jan 07 '16 at 14:59

5

A somewhat different approach, which uses integer arithmetic instead of comparisons (which wasn't explicitly prohibited)

for(int i=0;i<N;i++) {
  xmin += x[i]-xmin & x[i]-xmin>>31;
  xmax += x[i]-xmax & xmax-x[i]>>31;
}

answered Jan 07 '16 at 14:59

Anton Knyazyev

464
4
7

a-b is <0 if a=0 otherwise, so a-b>>31 is -1 (~0) in the former case and 0 in the latter. >>31 basically just propagates the sign bit to the entire number. so you get a + (b - a & mask), which is a+0=a if mask is 0 and a+b-a=b if mask is ~0 – Anton Knyazyev Mar 20 '17 at 13:21

Rocky Scott · Answer 5 · 2021-02-17T21:42:57.533

Brute-force is FASTER!

I would love someone to show me the error of my ways, here, but, …

I compared the actual run times of the brute-force method vs. the (more beautiful) recursive divide and conquer. Typical results (in 10,000,000 calls to each function):

Brute force :
  0.657 seconds 10 values => 16 comparisons.  Min @ 8, Max @ 10
  0.604 seconds 1000000 values => 1999985 comparisons.  Min @ 983277, Max @ 794659
Recursive :
  1.879 seconds 10 values => 13 comparisons.  Min @ 8, Max @ 10
  2.041 seconds 1000000 values => 1499998 comparisons.  Min @ 983277, Max @ 794659

Surprisingly, the brute-force method was about 2.9 times faster for an array of 10 items, and 3.4 times faster for an array of 1,000,000 items.

Evidently, the number of comparisons is not the problem, but possibly the number of re-assignments, and the overhead of calling a recursive function (I have no idea why 1,000,000 values ran faster than 10 values, but it did!).

Caveats : I did this in VBA, not C, and I was comparing double-precision numbers and returning the index into the array of the Min and Max values.

Here is the code I used (class cPerformanceCounter is not included here but uses QueryPerformanceCounter for high-resolution timing) :

Option Explicit

'2021-02-17

Private Const MIN_LONG As Long = -2147483648#

Private m_l_NumberOfComparisons As Long

Sub Time_MinMax()

   Const LBOUND_VALUES As Long = 1

   Dim l_pcOverall As cPerformanceCounter
   Dim l_d_Values() As Double
   Dim i As Long, _
       k As Long, _
       l_l_UBoundValues As Long, _
       l_l_NumberOfIterations As Long, _
       l_l_IndexOfMin As Long, _
       l_l_IndexOfMax As Long

   Set l_pcOverall = New cPerformanceCounter

   For k = 1 To 2

      l_l_UBoundValues = IIf(k = 1, 10, 1000000)

      ReDim l_d_Values(LBOUND_VALUES To l_l_UBoundValues)

      'Assign random values
      Randomize '1 '1 => the same random values to be used each time
      For i = LBOUND_VALUES To l_l_UBoundValues
         l_d_Values(i) = Rnd
      Next i
      For i = LBOUND_VALUES To l_l_UBoundValues
         l_d_Values(i) = Rnd
      Next i

      'This keeps the total run time in the one-second neighborhood
      l_l_NumberOfIterations = 10000000 / l_l_UBoundValues

      '——————— Time Brute Force Method —————————————————————————————————————————
      l_pcOverall.RestartTimer

      For i = 1 To l_l_NumberOfIterations

         m_l_NumberOfComparisons = 0

         IndexOfMinAndMaxDoubleBruteForce _
               l_d_Values, _
               LBOUND_VALUES, _
               l_l_UBoundValues, _
               l_l_IndexOfMin, _
               l_l_IndexOfMax

      Next

      l_pcOverall.ElapsedSecondsDebugPrint _
            3.3, , _
            " seconds Brute-Force " & l_l_UBoundValues & " values => " _
            & m_l_NumberOfComparisons & " comparisons. " _
            & " Min @ " & l_l_IndexOfMin _
            & ", Max @ " & l_l_IndexOfMax, _
            True
      '——————— End Time Brute Force Method —————————————————————————————————————

      '——————— Time Brute Force Using Individual Calls —————————————————————————
      l_pcOverall.RestartTimer

      For i = 1 To l_l_NumberOfIterations

         m_l_NumberOfComparisons = 0

         l_l_IndexOfMin = IndexOfMinDouble(l_d_Values)
         l_l_IndexOfMax = IndexOfMaxDouble(l_d_Values)

      Next

      l_pcOverall.ElapsedSecondsDebugPrint _
            3.3, , _
            " seconds Individual  " & l_l_UBoundValues & " values => " _
            & m_l_NumberOfComparisons & " comparisons. " _
            & " Min @ " & l_l_IndexOfMin _
            & ", Max @ " & l_l_IndexOfMax, _
            True
      '——————— End Time Brute Force Using Individual Calls —————————————————————

      '——————— Time Recursive Divide and Conquer Method ————————————————————————
      l_pcOverall.RestartTimer

      For i = 1 To l_l_NumberOfIterations

         m_l_NumberOfComparisons = 0

         IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
               l_d_Values, _
               LBOUND_VALUES, _
               l_l_UBoundValues, _
               l_l_IndexOfMin, l_l_IndexOfMax

      Next

      l_pcOverall.ElapsedSecondsDebugPrint _
            3.3, , _
            " seconds Recursive   " & l_l_UBoundValues & " values => " _
            & m_l_NumberOfComparisons & " comparisons. " _
            & " Min @ " & l_l_IndexOfMin _
            & ", Max @ " & l_l_IndexOfMax, _
            True
      '——————— End Time Recursive Divide and Conquer Method ————————————————————

   Next k

End Sub

'Recursive divide and conquer
Sub IndexOfMinAndMaxDoubleRecursiveDivideAndConquer( _
      i_dArray() As Double, _
      i_l_LBound As Long, _
      i_l_UBound As Long, _
      o_l_IndexOfMin As Long, _
      o_l_IndexOfMax As Long)

   Dim l_l_IndexOfLeftMin As Long, _
       l_l_IndexOfLeftMax As Long, _
       l_l_IndexOfRightMin As Long, _
       l_l_IndexOfRightMax As Long, _
       l_l_IndexOfMidPoint As Long

   If (i_l_LBound = i_l_UBound) Then 'Only one element

      o_l_IndexOfMin = i_l_LBound
      o_l_IndexOfMax = i_l_LBound

   ElseIf (i_l_UBound = (i_l_LBound + 1)) Then 'Only two elements

      If (i_dArray(i_l_LBound) > i_dArray(i_l_UBound)) Then
         o_l_IndexOfMin = i_l_UBound
         o_l_IndexOfMax = i_l_LBound
      Else
         o_l_IndexOfMin = i_l_LBound
         o_l_IndexOfMax = i_l_UBound
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   Else 'More than two elements => recurse

      l_l_IndexOfMidPoint = (i_l_LBound + i_l_UBound) / 2

      'Find the min of the elements in the left half
      IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
            i_dArray, _
            i_l_LBound, _
            l_l_IndexOfMidPoint, _
            l_l_IndexOfLeftMin, _
            l_l_IndexOfLeftMax

      'Find the min of the elements in the right half
      IndexOfMinAndMaxDoubleRecursiveDivideAndConquer i_dArray, _
            l_l_IndexOfMidPoint + 1, _
            i_l_UBound, _
            l_l_IndexOfRightMin, _
            l_l_IndexOfRightMax

      'Return the index of the lower of the two values returned
      If (i_dArray(l_l_IndexOfLeftMin) > i_dArray(l_l_IndexOfRightMin)) Then
         o_l_IndexOfMin = l_l_IndexOfRightMin
      Else
         o_l_IndexOfMin = l_l_IndexOfLeftMin
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

      'Return the index of the lower of the two values returned
      If (i_dArray(l_l_IndexOfLeftMax) > i_dArray(l_l_IndexOfRightMax)) Then
         o_l_IndexOfMax = l_l_IndexOfLeftMax
      Else
         o_l_IndexOfMax = l_l_IndexOfRightMax
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   End If

End Sub

Sub IndexOfMinAndMaxDoubleBruteForce( _
      i_dArray() As Double, _
      i_l_LBound As Long, _
      i_l_UBound As Long, _
      o_l_IndexOfMin As Long, _
      o_l_IndexOfMax As Long)

   Dim i As Long

   o_l_IndexOfMin = i_l_LBound
   o_l_IndexOfMax = o_l_IndexOfMin

   For i = i_l_LBound + 1 To i_l_UBound

      'Usually we will do two comparisons
      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 2

      If (i_dArray(i) < i_dArray(o_l_IndexOfMin)) Then

         o_l_IndexOfMin = i

         'We don't need to do the ElseIf comparison
         m_l_NumberOfComparisons = m_l_NumberOfComparisons - 1

      ElseIf (i_dArray(i) > i_dArray(o_l_IndexOfMax)) Then

         o_l_IndexOfMax = i

      End If
   Next i

End Sub

Function IndexOfMinDouble( _
      i_dArray() As Double _
      ) As Long

   Dim i As Long

   On Error GoTo EWE

   IndexOfMinDouble = LBound(i_dArray)

   For i = IndexOfMinDouble + 1 To UBound(i_dArray)

      If (i_dArray(i) < i_dArray(IndexOfMinDouble)) Then
         IndexOfMinDouble = i
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   Next i

   On Error GoTo 0
   Exit Function
EWE:
   On Error GoTo 0
   IndexOfMinDouble = MIN_LONG
End Function

Function IndexOfMaxDouble( _
      i_dArray() As Double _
      ) As Long

   Dim i As Long

   On Error GoTo EWE

   IndexOfMaxDouble = LBound(i_dArray)

   For i = IndexOfMaxDouble + 1 To UBound(i_dArray)

      If (i_dArray(i) > i_dArray(IndexOfMaxDouble)) Then
         IndexOfMaxDouble = i
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   Next i

   On Error GoTo 0
   Exit Function
EWE:
   On Error GoTo 0
   IndexOfMaxDouble = MIN_LONG
End Function

1. This is not how benchmarking is done. 2. On small samples brute force may work better. 3. If what you claim was true, then how can you explain the math behind time-complexity calculations that prove that brute-force sorting of an array takes O(n^2) while "smart" sorts like merge-sort take O(nlogn)? Should we throw away all we learned in Algorithm class on CS? :) — Nir Alfasi, Feb 16 '21 at 16:59
@Nir: 1) How is benchmarking done? 2) 10^6 samples seems pretty large to me. My post suggests an explanation in the paragraph beginning with "Evidently". I don't "throw away" any learning, but I do test everything. When dealing with a real computer, additional considerations may overwhelm a simplistic mathematical calculation that ignores memory allocation, etc. This may be especially true in this case where the comparisons and reassignments are only a few CPU instructions, while the overhead of a recursive function is comparatively huge. So, this is my GUESS. Am I all wet? (Be kind. I'm old.) — Rocky Scott, Feb 17 '21 at 21:38
A useful caveat. Then again, the question reads `minimum comparisons`. — greybeard, Feb 18 '21 at 05:29
@RockyScott my guess is as good as yours but I would also suspect that the recursion overhead (opening a new frame on the stack for every recursive call) is the main factor. — Nir Alfasi, Feb 18 '21 at 14:03

P_P · Answer 6 · 2016-11-13T16:37:16.433

After reading the question and answers, I decided to try a few versions (in C#).
I thought the fastest would be Anton Knyazyev's one (branch free), it isn't (on my box).
Results:

/*                comp.  time(ns)
      minmax0     3n/2    855
      minmax1     2n      805
      minmax2     2n     1315 
      minmax3     2n      685          */

Why are minmax1 and minmax3 faster? Probably because the "branch predictor" does a nice job, each iteration the chance, a new min (or max) is found, decreases, so predictions become better.
All in all it's a simple test. I do realize my conclusions may be:
-premature.
-not valid for different platforms.
Let's say they're indicative.
Edit: Break-even point minmax0, minmax3: ~100 items,
10,000 items: minmax3 ~3.5 times faster than minmax0.

using System;
using sw = System.Diagnostics.Stopwatch;
class Program
{
    static void Main()
    {
        int n = 1000;
        int[] a = buildA(n);
        sw sw = new sw();
        sw.Start();
        for (int i = 1000000; i > 0; i--) minMax3(a);
        sw.Stop();
        Console.Write(sw.ElapsedMilliseconds);
        Console.Read();
    }

    static int[] minMax0(int[] a)  // ~3j/2 comp.
    {
        int j = a.Length - 1;
        if (j < 2) return j < 0 ? null :
            j < 1 ? new int[] { a[0], a[0] } :
            a[0] < a[1] ? new int[] { a[0], a[1] } :
                          new int[] { a[1], a[0] };
        int a0 = a[0], a1 = a[1], ai = a0;
        if (a1 < a0) { a0 = a1; a1 = ai; }
        int i = 2;
        for (int aj; i < j; i += 2)
        {
            if ((ai = a[i]) < (aj = a[i + 1]))  // hard to predict
            { if (ai < a0) a0 = ai; if (aj > a1) a1 = aj; }
            else
            { if (aj < a0) a0 = aj; if (ai > a1) a1 = ai; }
        }
        if (i <= j)
        { if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
        return new int[] { a0, a1 };
    }

    static int[] minMax1(int[] a)  // ~2j comp.  
    {
        int j = a.Length;
        if (j < 3) return j < 1 ? null :
            j < 2 ? new int[] { a[0], a[0] } :
            a[0] < a[1] ? new int[] { a[0], a[1] } :
                          new int[] { a[1], a[0] };
        int a0 = a[0], a1 = a0, ai = a0;
        for (int i = 1; i < j; i++)
        {
            if ((ai = a[i]) < a0) a0 = ai;
            else if (ai > a1) a1 = ai;
        }
        return new int[] { a0, a1 };
    }

    static int[] minMax2(int[] a)  // ~2j comp.  
    {
        int j = a.Length;
        if (j < 2) return j == 0 ? null : new int[] { a[0], a[0] };
        int a0 = a[0], a1 = a0;
        for (int i = 1, ai = a[1], aj = ai; ; aj = ai = a[i])
        {
            ai -= a0; a0 += ai & ai >> 31;
            aj -= a1; a1 += aj & -aj >> 31;
            i++; if (i >= j) break;
        }
        return new int[] { a0, a1 };
    }

    static int[] minMax3(int[] a)  // ~2j comp.
    {
        int j = a.Length - 1;
        if (j < 2) return j < 0 ? null :
            j < 1 ? new int[] { a[0], a[0] } :
            a[0] < a[1] ? new int[] { a[0], a[1] } :
                          new int[] { a[1], a[0] };
        int a0 = a[0], a1 = a[1], ai = a0;
        if (a1 < a0) { a0 = a1; a1 = ai; }
        int i = 2;
        for (j -= 2; i < j; i += 3)
        {
            ai = a[i + 0]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
            ai = a[i + 1]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
            ai = a[i + 2]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
        }
        for (j += 2; i <= j; i++)
        { if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
        return new int[] { a0, a1 };
    }

    static int[] buildA(int n)
    {
        int[] a = new int[n--]; Random rand = new Random(0);
        for (int j = n; n >= 0; n--) a[n] = rand.Next(-1 * j, 1 * j);
        return a;
    }
}

score 2 · Answer 7 · answered Nov 16 '14 at 06:06

A simple pseudo code for the recursive algorithm:

Function MAXMIN (A, low, high)
    if (high − low + 1 = 2) then 
      if (A[low] < A[high]) then
         max = A[high]; min = A[low].
         return((max, min)).
      else
         max = A[low]; min = A[high].
         return((max, min)).
      end if
   else
      mid = low+high/2
      (max_l , min_l ) = MAXMIN(A, low, mid).
      (max_r , min_r ) =MAXMIN(A, mid + 1, high).
   end if

   Set max to the larger of max_l and max_r ; 
   likewise, set min to the smaller of min_l and min_r .

   return((max, min)).

score 1 · Answer 8 · answered Jan 07 '16 at 07:25

import java.util.*;
class Maxmin
{
    public static void main(String args[])
    {
        int[] arr = new int[10];
        Scanner in = new Scanner(System.in);
        int i, min=0, max=0;
        for(i=0; i<=9; i++)
        {
            System.out.print("Enter any number: ");
            arr[i] = in.nextInt();          
        }
        min = arr[0];
        for(i=0; i<=9; i++)
        {
            if(arr[i] > max)
            {
                max = arr[i];
            }
            if(arr[i] < min)
            {
                min = arr[i];
            }
        }
        System.out.println("Maximum is: " + max);
        System.out.println("Minimum is: " + min);
    }
}

This is the trivial `2n` comparison method, OP is looking for solutions with lower asymptotic runtimes. — zstewart, Aug 18 '16 at 15:01

anisotropic · Answer 9 · 2016-10-31T09:05:07.963

My divide & conquer approach with java so far:

        public class code {    
    static int[] A = {444,9,8,6,199,3,0,5,3,200};
    static int min = A[0], max = A[1];
    static int count = 0;

    public void minMax(int[] A, int i, int j) {     
        if(i==j) {
            count = count + 2;
            min = Math.min(min, A[i]);
            max = Math.max(max, A[i]);
        }

        else if(j == i+1) {
            if(A[i] > A[j]) {
                count = count + 3;
                min = Math.min(min, A[j]);
                max = Math.max(max, A[i]);
            }
            else {
                count = count + 3;
                min = Math.min(min, A[i]);
                max = Math.max(max, A[j]);
            }
        }

        else {
            minMax(A,i,(i+j)/2);
            minMax(A,(i+j)/2+1,j);
        }
    }

    public static void main(String[] args) {
        code c = new code();
        if(Math.min(A[0], A[1]) == A[0]) {
            count++;
            min = A[0];
            max = A[1];
        }
        else {
            count++;
            min = A[1];
            max = A[0];
        }
        c.minMax(A,2,A.length-1);
        System.out.println("Min: "+min+" Max: "+max);
        System.out.println("Total comparisons: " + count);
    }
}

score 1 · Answer 10 · answered Jan 05 '17 at 23:47

public static int[] minMax(int[] array){
    int [] empty = {-1,-1};
    if(array==null || array.length==0){
        return empty;
    }

    int lo =0, hi = array.length-1;
    return minMax(array,lo, hi); 

}

private static int[] minMax(int []array, int lo, int hi){

    if(lo==hi){
        int [] result = {array[lo], array[hi]}; 
        return result;
    }else if(lo+1==hi){
        int [] result = new int[2];
        result[0] = Math.min(array[lo], array[hi]);
        result[1] = Math.max(array[lo], array[hi]);
        return result;
    }else{
        int mid = lo+(hi-lo)/2;          
        int [] left = minMax(array, lo, mid);
        int [] right = minMax(array, mid+1, hi);
        int []result = new int[2];          
        result[0] = Math.min(left[0], right[0]);
        result[1] = Math.max(left[1], right[1]);             
        return result;
    }

}

public static void main(String[] args) {

    int []array = {1,2,3,4,100};
    System.out.println("min and max values are "+Arrays.toString(minMax(array)));
}

score 1 · Answer 11 · answered May 11 '17 at 05:05

1

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    set<int> t;
    for(int i=0;i<n;i++)
    {

        int x;
        cin>>x;
        t.insert(x);
    }
    set<int>::iterator s,b;
    s=t.begin();
    b=--t.end();
    cout<< *s<<" "<<*b<<endl;


    enter code here

    return 0;
}

// this can be done in log(n) complexity!!!

answered May 11 '17 at 05:05

saurabh kumar

174
1
5

You're effectively sorting the list. Each insertion is log(n), and it's done for each element, so you haven't beaten the O(n*log(n)) bound on comparison-based sorting. – Arya McCarthy May 11 '17 at 05:31

Eduard · Answer 12 · 2019-11-07T07:40:51.230

if (numbers.Length <= 0)
{
    Console.WriteLine("There are no elements");
    return;
}

if (numbers.Length == 1)
{
    Console.WriteLine($"There is only one element. So min and max of this 
                        array is: {numbers[0]}");
    return;
}

if (numbers.Length == 2)
{
    if (numbers[0] > numbers[1])
    {
        Console.WriteLine($"min = {numbers[1]}, max = {numbers[0]}");
        return;
    }

    Console.WriteLine($"min = {numbers[0]}, max = {numbers[1]}");
    return;
}

int i = 0;
int j = numbers.Length - 1;

int min = numbers[i];
int max = numbers[j];
i++;
j--;

while (i <= j)
{
    if(numbers[i] > numbers[j])
    {
        if (numbers[j] < min) min = numbers[j];
        if (numbers[i] > max) max = numbers[i];
    }
    else
    {
        if (numbers[i] < min) min = numbers[i];
        if (numbers[j] > max) max = numbers[j];
    }
    i++;
    j--;
}

It's a solution written in C#. I find this method of burning the candle at both ends to be a good contender as a solution.

score 1 · Answer 13 · answered Oct 17 '20 at 02:03

Compare in Pairs will work best for minimum comparisons

# Initialization # 
- if len(arr) is even, min = min(arr[0], arr[1]), max = max(arr[0], arr[1])
- if len(arr) is odd, min = min = arr[0], max = arr[0]

# Loop over pairs # 
- Compare bigger of the element with the max, and smaller with min,
- if smaller element less than min, update min, similarly with max.

Total Number of comparisons -

For size = odd, 3(n - 1) / 2 where n is size of array
For size = even, 1 + 3*(n - 2)/2 = 3n/2 - 2

Below is the python code for the above pseudo-code

class Solution(object):
    def min_max(self, arr):
        size = len(arr)
        if size == 1:
            return arr[0], arr[0]

        if size == 2:
            return arr[0], arr[1]

        min_n = None
        max_n = None
        index = None
        if size % 2 == 0:       # One comparison
            min_n = min(arr[0], arr[1])
            max_n = max(arr[0], arr[1])
            st_index = 2

        else:
            min_n = arr[0]
            max_n = arr[0]
            st_index = 1
        for index in range(st_index, size, 2):
            if arr[index] < arr[index + 1]:
                min_n = min(arr[index], min_n)
                max_n = max(arr[index + 1], max_n)
            else:
                min_n = min(arr[index + 1], min_n)
                max_n = max(arr[index], max_n)

        return min_n, max_n

score -5 · Answer 14 · answered Nov 24 '12 at 18:58

-5

Just loop over the array once, keeping track of the max and min so far.

answered Nov 24 '12 at 18:58

pauljwilliams

19,079
3
51
79

2

Without further specification, I have to assume this does two comparisions for each element, and thus also does 2n comparisions. – Nov 24 '12 at 19:02
That's not minimum comparisions – Samarth Juneja Jun 07 '20 at 15:59

How to find max. and min. in array using minimum comparisons?

14 Answers14

Linked

Related