Saturday, February 25, 2012

Get the Max and Min Simultaneously

Problem: Given an array of integers, try to get the max and min in this array with the least number of comparisons.

Solutions:  if we have a current_max and current_min, for each element except the first one, we need to compare it against current_max and current_min. Thus in total, we need 2n-2 comparisons (or 2n-3 if you do it slightly different). However, a better approach exists by inspecting the integers in pair. We first compare the two adjacent integers, and use the bigger one from the two to compare against current_max and use the smaller one from the two to compare against current_min. For example, if A[i] = 4, A[i+1] = 10 and current_max = 11 and current_min = 2,  we just need to compare A[i] against current_min and A[i] against current_max. Therefore, for every two integers, we need 3 comparisons, which leads to a total comparisons around 3n/2.

1 comment:

  1. Thanks, we've added this your solution here: