Find Max and Min in array

Given an array of integers, how to find the maximum and minimum?

Simple solution:

C++:
01 void maxmin(int *A, int size, int& max, int &min)
02 {
03     max=min=A[0];
04     for(int i=1;i<size;i++){
05         if(max<A[i])
06             max=A[i];
07         if(min>A[i])
08             min=A[i];
09     }
10 }
Further thought, can we reduce the comparing number? The above approach require 2n comparing in worst case.
Alternative solution:
1.Build n/2 pairs, compare two element for each pair. We can get a max set and min set which composed by the max and min element in each pair.
2.Find the max in the max set and min in the min set.
Number of comparing: n/2+n/2+n/2=3n/2.
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s