# 3n/2 comparisons to find the smallest and largest numbers in the list

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:

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)