**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.

Thanks, we've added this your solution here: https://github.com/EvgenyKarkan/EKAlgorithms/issues/30

ReplyDelete