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;
}
else
{
if (v2 > max) max = v2;
if (v1 < min) min = v1;
}
}

Comments

AlexSusu

<p>Nice "hack". It sort of reminds me (distantly) of an optimization performed on the MergeSort algorithm in order to be able to sort in O(N) a vector that is already sorted (see the book of Sedgewick on Algorithms, IIRC). Also another amazing hack is in the same book [CLRS-3rd edition] at Finding Pair of Closest Points in 2D.</p>

AlexSusu

Post a comment