Thursday, August 11, 2016

Finding simultaneously the minimum and maximum, optimized

While reading the book Introduction to Algorithms, Third Edition, by Thomas H. Cormen and Charles E. Leiserson, I found a little gem about simultaneously finding the minimum and maximum value in an array in 3*n/2 comparisons instead of the usual 2n. The trick is to take two numbers at a time, compare them with each other and only then compare the smallest one with the minimum and the largest with the maximum.

So instead of:
var min=int.MaxValue;
var max=int.MinValue;
for (var i=0; i<arr.Length; i++) {
   var val=arr[i];
   if (val>max) max=val;
   if (val<min) min=val;
you can use this:
var min=int.MaxValue;
var max=int.MinValue;
for (var i=0; i<arr.Length-1; i+=2) {
   var v1=arr[i];
   var v2=arr[i+1];
   if (v1>v2) {
      if (v1>max) max=v1;
      if (v2<min) min=v2;
   } else {
      if (v2>max) max=v2;
      if (v1<min) min=v1;
if (arr.Length%2==1) {
   var v=arr[arr.Length-1];
   if (v>max) max=v;
   if (v<min) min=v;

In the first case, we take all n values and compare them with the min and max values respectively, so n times 2. In the second example we take every two values (so n/2 times), compare them with each other (1 comparison) and then we compare the smaller value with min and the larger with max (another 2 comparisons), with a combined number of comparisons of n/2 times 3 (plus 2 extra ones if the number of items in the array is odd).

Update: Here is a variant for an IEnumerable<int>, the equivalent of a foreach:
var enumerator = enumerable.GetEnumerator();
var min = int.MaxValue;
var max = int.MinValue;
while (enumerator.MoveNext()) {
    var v1 = enumerator.Current;
    var v2 = enumerator.MoveNext() ? enumerator.Current : v1;
    if (v1 > v2)
        if (v1 > max) max = v1;
        if (v2 < min) min = v2;
        if (v2 > max) max = v2;
        if (v1 < min) min = v1;