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)