# 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, seq
if len(seq) % 2 != 0:
seq = seq[1:]
''' Initalising mini and maxi as seq gives us the redundancy to
remove it from any seq with an odd length '''
while len(seq) > 1:
if seq < seq:
if mini >= seq:
mini = seq
if maxi <= seq:
maxi = seq
else:
if mini >= seq:
mini = seq
if maxi <= seq:
maxi = seq
''' 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)

```