Ticklish Techs

Here is a nice little challenge, Benjamin came up with some months ago: “From a list of numbers find the smallest and the largest one – but do not use more than 1,5 comparisons per number.”

Dear reader: Try it!

The solution is simple, straight forward and very nice. And I didn’t find it.

I found something else. My approach was to look at the largest-number-so-far (max) and the smallest-number-so-far (min) as the boundaries of a region. A number outside this region must be larger than max or smaller than min and causes that boundary to change.

To check if a number (a) was outside that region a little computation came to my mind:

check = (max - a)*(min - a);

You would expect n to be smaller than max, so (max-n) should be positive.

You would expect n to be larger than min, so (n-min) should be positive, too.

Two positive numbers multiplied result in a positive number again.

So, if n was outside the boundaries, check would become negative. I only had to check which boundary was exceeded and that’s it:

if (check < 0)
    if (a > max)
        max = a;
    else
        min = a;

Using this approach the number of comparisons  converges to 1 when the length of the list grows. So I found a solution that is way better than 1,5 comparisons per number, didn’t I?

Boooooh

No, I didn’t. I cheated. In fact  (max-a) and (min-a) are comparisons, they just don’t use > or <.

(Actually it’s the other way around: To compute < or > most processors do a subtraction and compare the result to 0.)

So – if you count the subtractions as well you get 3+ comparisons per number…

The intended solution to the challenge (and the code you should provide in your exam) is:

a = list[count++];
b = list[count++];

if (a<b)
{
    if (a<min) min = a;
    if (b>max) max = b;
}
else
{
    if (b < min) min = b;
    if (a > max) max = a;                    
}

So – what’s the point of this post?

The point is: My silly approach can be faster than the standard solution. Depending on the type and range of the numbers in the list calculating and probing check needs less time than the comparisons in the standard solution.

It may not be much, but sometimes small advantages matter.  For example: For an integer-list of length 10^8 with values from -10.000 to 10.000 my approach is 0.02 seconds faster (on my current laptop). And has less code.

So if you feel like using it – I won’t charge you.