snippetMinor
How do I find the max and min value of an array in 3n/2−2 comparisons?
Viewed 0 times
thehowarrayvalueminmaxfindandcomparisons
Problem
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.
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.
Solution
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.
... assuming, of course, you have an even total number of elements. Think about what happens if that isn't the case.
Context
StackExchange Computer Science Q#52663, answer score: 7
Revisions (0)
No revisions yet.