Hi again!

1) Okay, I see. So I learned something about Python finally… hope I won’t be sent to hell for it.
2) I would have accepted Prolog or Lisp perfecly… well at least I could have read it…

Okay, I’ll check out your code soon.

using System;
using System.Collections.Generic;

namespace MinMax
{
    class Program
    {
        public static int Counter { get; set; }

        public static int[] Range( int fromIncl, int toExcl )
        {
            int inc = fromIncl < toExcl ? 1 : -1;
            var len = Math.Abs(toExcl - fromIncl);
            var result = new int[len];
            for( int pos=0, val=fromIncl; pos < len; ++pos, val+=inc )
                result[pos] = val;
            return result;
        }

        public static int[] Subrange( int[] arr, int fromIncl, int toExcl )
        {
            var len = toExcl - fromIncl;
            var result = new int[len];
            for (int pos = 0; pos < len; ++pos)
                result[pos] = arr[fromIncl + pos];
            return result;
        }

        public static KeyValuePair MinMax( int[] arr )
        {
            if( arr.Length == 1 )
                return new KeyValuePair(arr[0],arr[0]);
            if( arr.Length == 2 )
            {
                Counter = Counter + 1;
                if( arr[0] < arr[1] )
                    return new KeyValuePair(arr[0], arr[1]);
                return new KeyValuePair(arr[1], arr[0]);
            }
            var mid = arr.Length/2;
            var left = MinMax(Subrange(arr, 0, mid));
            var right = MinMax(Subrange(arr, mid, arr.Length));
            Counter = Counter + 2;            
            return new KeyValuePair( Math.Min(left.Key,right.Key), Math.Max(left.Value,right.Value));
        }

        static void Main()
        {
            Counter = 0;
            Console.Out.WriteLine(MinMax(Range(0, 16)));
            Console.Out.WriteLine( "comparisons: " + Counter );
            Counter = 0;
            Console.Out.WriteLine(MinMax(Range(16, 0)));
            Console.Out.WriteLine("comparisons: " + Counter);
        }
    }
}

[/code]
I tried to put some lambda and linq in it, but the only reasonable way was:
var min = arr.Min();
var max = arr.Max();
😉

Ah… now I understand… but I have some questions.

1)
Doesn’t the part:

left = minmax( list[0:mid] )
right = minmax( list[mid:])

copy the ‘mid’-element?

This doesn’t influence the result, but results in a bad in influence (more work to do).

2)
I think the code isn’t correct.

left = minmax( list[0:mid] )
    right = minmax( list[mid:])
    min = left[0]
    minmax.counter = minmax.counter + 1
    if right[0]  max:
        max = right[1]

What about the min-result of right? And the max-result of left?
So I think

sample = range( 16, 0 )

leads to a wrong result.

Greets,
Wolfram

Hi Franz!

That looks very interesting. Thanks a lot!
Unfortunately I am not sure I understand what list[0] means… Could you please provide this example in a reasonable programming language? 🙂

Greets,
Wolfram

def minmax( list ):
    if len(list) == 1:
        return ( list[0], list[0] )
    if len(list) == 2:
        minmax.counter = minmax.counter + 1
        if list[0] > list[1]:
            return (list[1], list[0] )
        return (list[0], list[1] )
    mid = len(list) / 2
    left = minmax( list[0:mid] )
    right = minmax( list[mid:])
    min = left[0]
    minmax.counter = minmax.counter + 1
    if right[0]  max:
        max = right[1]
    return (min,max)

minmax.counter = 0
sample = range( 0, 16 )
print minmax( sample )
print minmax.counter

( that’s no code fragment, but the hole thing! )
I leave the proof, that this will always needs LESS that 1.5 n comparisons as an exercise 😉