Monday, March 14, 2011

Finding max and min

Q: Given an array of n elements, find the min and max in 3n/2 comparisons even in worst case.

We usually think of the following approach as soon as we see the question

One scan through the array with two extra variables to store current min and max.
In this approach the worst case number of comparisons = 2n

Can we change the approach slightly to make sure that even the worst case number of comparisons is 3*n/2

Following is the approach..

1) take 2 number at a time ....

2) compare these 2 numbers .... (1st comparison)

3) compare the minimum of these two with current minimum  (2nd comparison)

4) compare the max of these two with current max (3rd comparison)

as there are (n/2) pairs ... and 3 comparisons per a pair .... total comparisons are 3n/2 ....

No comments: