Finding minimum and maximum value in Array in single pass…

globetrotter

To find the minimum value into an array of items, take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.

We pass through the array with n steps and we need exactly n-1 comparisons.

Finding the maximum is identical to finding the minimum and requires n-1 comparisons!

Since they both are O(n) and need n-1 comparisons it’s natural to think that combining the two tasks will be O(n) and 2n – 2 comparisons. However we can reduce the number of comparisons!

Instead of taking only one item from the array and comparing it against the minimum and maximum we can take a pair of items at each step. Thus we can first compare them and then compare the smaller value with the currently smallest value and…

View original post 62 more words

Advertisements

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 17, 2013, in Algorithms, Programming and tagged . Bookmark the permalink. Leave a comment.

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

%d bloggers like this: