5
$\begingroup$

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers or a single number.

What I'm trying to do now is the same thing but I'm trying to come up with a method that will always use 3n/2−2 comparisons. The method above doesn't use 3n/2−2 comparisons each time. So I just want to visualize how this is done on an array before I start to programming the method.

Improve this question
$\endgroup$
3
  • $\begingroup$ Why? What's the purpose? Why don't you do the trivial linear scan with $n-1$ comparisons? $\endgroup$ – Raphael♦ Feb 4 '16 at 7:43
  • 1
    $\begingroup$ @Raphael I believe the OP wants to compute minimum and maximum simultaneously, i.e. in one pass over an array. Moreover there is a well-known algorithm (see CLRS (3d edition), sect. 9.1, p. 214). Its total number of comparisons is at most $3 \lfloor n / 2 \rfloor$. There is also a proof that we cannot do better (can't find the reference to it now, Alex Stepanov gives it in one of his freely available videolectures). $\endgroup$ – Anton Trunov Feb 4 '16 at 8:06
  • $\begingroup$ @AntonTrunov Ah, true enough. My mistake, thanks for clearing that up! $\endgroup$ – Raphael♦ Feb 4 '16 at 9:26
7
$\begingroup$

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. The maximum value of the original array must be the max of the larger group and the minimum value of the original array must be the min of the smaller group. Initially, you do n/2 comparisons to make the split, and from there you need to find the max and min of two groups of n/2 elements each, which can be done with a total of n/2 - 1 comparisons per group. Overall, this is 3n / 2 - 2 compares.

... assuming, of course, you have an even total number of elements. Think about what happens if that isn't the case.

Improve this answer
$\endgroup$
1
$\begingroup$

There is an algorithm for finding minimum and maximum simultaneously (in one pass over an array), requiring $O(1)$ additional memory.

The idea is to process the elements of the input array in pairs as in this answer by templatetypedef, but without explicit grouping, so (almost) no additional memory is needed.

A coarse sketch of the algorithm:

  1. Compare the first pair of elements between each other.

  2. Compare the smaller element with the current minimum and update the current minimum if needed.

  3. Compare the larger element with the current maximum and update the current maximum if needed.

  4. Repeat for the rest pairs.

The analysis of the number of comparisons is the same as given by @templatetypedef.

This algorithm is described in detail in "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (sect. 9.1, p. 214).

The book also states (in the form of an exercise) that the lower bound for any simultaneous min/max algorithm is $\lceil 3n/2 \rceil - 2$ comparisons in the worst case, so we actually can't do much better than we already do.

Improve this answer
$\endgroup$
0
$\begingroup$

Just scan the array, starting with provisional maximum and minimum as the first element, from the second element onwards. If the element is larger than your current maximum, record that; if not, see if it is smaller than your current minimum, and update. You don't need the whole paraphernalia of splitting and recursion.

Can't have a simpler program. Can't do with less work, need to compare with at least $n - 1$ elements to confirm the maximum. For any order in which you check, by ordering the elements to be checked in decreasing order, you can force $2 (n - 1)$ comparisons.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Consider an array of n 0's. Won't this make 2n-2 comparisons? $\endgroup$ – templatetypedef Feb 4 '16 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.