如何找到马克斯。最小值比较的数组?

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.

显然，我可以遍历数组两次，在最坏的情况下使用~2n比较，但我希望做得更好。

12 个解决方案

#1

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.

这样你就可以对2个元素做3个比较，总共是N个元素的3N/2个比较。

#2

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

试图改进srbh.kmr的答案。假设我们有序列:

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

Compare a1 & a2 and calculate min12, max12:

比较a1 & a2，计算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...

同样计算min34 max34。因为a5是单独的，所以保持它。

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

现在比较min12和min34，并计算min14，同样计算max14。最后比较min14和a5，计算min15。同样计算max15。

Altogether it's only 6 comparisons!

总共只有6个比较!

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:

更新:这里是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.

现在我不能用N(数组中元素的数目)来确定比较的确切数目。但是很难看出一个人是如何在这么多的比较之下的。

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.

在这棵计算树的底部，我们从原始数组中生成成对的整数。所以我们有N / 2叶节点。对于每一个叶节点，我们只做1个比较。

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.

对于每个内部节点，我们进行两个比较。因此，我们有N - 2个比较。在叶节点的N / 2比较中，我们有(3N / 2) - 2总比较。

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

所以，可能这就是解srbh。kmr暗示了他的答案。

#3

go for divide and conquer !

去分而治之!

1,3,2,5

1、3、2、5

for this finding min,max will take 6 comparisons

为了找到最小值，max将进行6次比较。

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

1、3 --->将在一个比较中给出最小值1和最大值3，在一个比较中，>将给出最小值2和最大值5。

now we can compare two mins (1,2) --> will give the final min as 1 ( one comparison) likewise two max(3,5) ---> will give the final max as 5( one comparison)

现在我们可以比较两分钟(1,2)->将最终的最小值为1(一个比较)同样的两个max(3,5) ->将给出最终的最大值为5(一个比较)

so totally four comparisons

所以完全四个比较

#4

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;
}

#5

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):

我比较了蛮力方法的实际运行时间和(更漂亮的)递归划分和征服。典型结果(10,000,000次调用每个函数):

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.

令人惊讶的是，对于10个条目的数组来说，brute-force方法的速度大约是2.9倍，而对于1,000,000个条目的数组则要快3.4倍。

Evidently, the number of comparisons is not the problem, but possibly the number of re-assignments, and the overhead of calling a recursive function (which might explain why 1,000,000 values runs slower than 10 values).

显然，比较的数量不是问题，但可能是重新分配的数量，以及调用递归函数的开销(这可能解释为什么1,000,000个值的运行速度低于10个值)。

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.

注意:我在VBA中这样做，而不是C，我在比较双精度数，并将索引返回到最小值和最大值的数组中。

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

这里是我使用的代码(class cperformance cecounter不包括在这里，而是使用queryperformance cecounter进行高分辨率的计时):

Option Explicit

'2014.07.02

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

#6

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)).

#7

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:

在阅读完问题和答案后，我决定尝试几个版本(在c#中)。我认为最快的应该是Anton Knyazyev的一个(分支免费)，它不是(在我的盒子里)。结果:

/*                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.

为什么minmax1和minmax3更快?很可能是因为“分支预测器”做的很好，每次迭代的机会，一个新的最小值(或最大值)被发现，减少，所以预测变得更好。总之，这是一个简单的测试。我确实意识到我的结论可能是:-不成熟。-对不同的平台无效。假设他们的象征。编辑:盈亏平衡点minmax0, minmax3: ~100项，10000个项目:minmax3 ~3.5倍于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;
    }
}

#8

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);
    }
}

#9

My divide & conquer approach with java so far:

到目前为止，我用java的分治方法是:

        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);
    }
}

#10

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)));
}

#11

#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!!!

//这可以用log(n)的复杂度来完成!!!

#12

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

只对数组进行一次循环，跟踪最大和最小值。