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)