Geek asks and answers

Maximum and minimum array values

An array of n numbers is given, where n is an even number. It is necessary to determine the maximum, as well as the minimum of these n numbers. I need to know what comparisons are needed?

+5
source share
3 answers

This can be done in O (n) time.

You can check this link for reference.

+3
source

This can be done using comparisons 3*n/2-2.

For n == 2just compare two numbers. Suppose now that we have a minimum and a maximum for the first numbers n-2. Compare the remaining two numbers, then compare the larger with the previous high and lower than the previous low.

+4
source

1.5n . , min max. n/2, (locals) max n/2, min. , n.

Now you go to max and min locals and find global max and min. It also involves comparison n/2. In this way n + n / 2 = 1.5n.

If the array is sorted, you can find it without any comparisons, since the lowest number is at position 0 and the highest is at position N - 1.

+1
source

More articles:


All Articles