After so much time studying for MIT6.00X and running through Rosalind problems I was rather frustrated to find the first exercise in An Introduction to Bioinformatics Algorithms below a bit tricky…

Design an algorithm that performs only 3n/2 comparisons to find the smallest and largest numbers in a list

As a linear search would end up performing 2n comparisons I looked at all sorts of ways to split the sequence up recursively but all my ideas ended up a bit messy and confused. After much longer than I would have liked I ended up:

• Pairing up my value into n/2 pairs
• Comparing the minimum value in each pair with the global minimum and vice versa with the maximum value

As such we see at most 3 comparisons for each pair of values giving us 3n/2 comparisons in total.

The only thing to be wary of is a sequence with an odd number of values, I think I have avoided the issue in the code below with a cheeky list slice and a bit of redundancy.

After fiddling with all sorts of messy ideas I settled for the following:

[code language=”python” wraplines=”false” collapse=”false”]

seq = [1,2,2,3,2,5,7,4,7,9,1,2,7]

def find_max_min(seq):
    mini,maxi = seq[0], seq[0]
    if len(seq) % 2 != 0:
        seq = seq[1:]
    ”’ Initalising mini and maxi as seq[0] gives us the redundancy to 
        remove it from any seq with an odd length ”’
    while len(seq) > 1:
        if seq[0] < seq[1]:
            if mini >= seq[0]:
                mini = seq[0]
            if maxi <= seq[1]:
                maxi = seq[1]
        else:
            if mini >= seq[1]:
                mini = seq[1]
            if maxi <= seq[0]:
                maxi = seq[0] 
        ”’ Here we are performing at most 3 comparisons 
            on each pair of items in our sequence ”’
        seq = seq[2:]
    return mini, maxi

print find_max_min(seq)

[/code]