This was a question I asked on reddit that I want to save
So I am looking over some past finals and this one kind-of sort-of stumped me, the question is:
Find an algorithm that makes less than n*3/2 comparison to find the largest and smallest value in a list of n values.
so I’m thinking Divide and Conquer approach, and I got the answer, however, it is for keys that fit the rule 2i + k where k is close to 0 and i is an integer. I’m not sure if there is another way of approaching the problem. to mess around with it, I decided to mock it up in python to test it out (which is where I determined that unless the number of items is close to function f(i) = 2i, it doesn’t really hold true)
import random
counter = [0] # global, mutable counter for counting the number of comparisons
def file_min_max(F, n=None):
if n is None:
n = len(F)
if n == 1:
return F[0], F[0]
elif n == 2:
counter[0] += 1
if F[0] < F[1]:
return F[0], F[1]
else:
return F[1], F[0]
else:
mid = n//2
left = file_min_max(F[0:mid])
right = file_min_max(F[mid:n])
counter[0] += 2
if left[0] > right[0]:
minimum = right[0]
else:
minimum = left[0]
if left[len(left)-1] > right[len(right)-1]:
maximum = right[len(left)-1]
else:
maximum = left[len(right)-1]
return minimum, maximum
# unit testing
test_list = []
num = 2**10 + 0 # modify the number of elements here
for i in range(num):
test_list.append(random.randint(0, num))
print(test_list)
print(file_min_max(test_list))
print(counter[0])
print(len(test_list))
print(counter[0]/len(test_list))
so my questions are:
1) is there another way of approaching this problem I didn’t see?
2) did I count my comparisons incorrectly?
also, as an aside, since this is a recursive function, I was using a mutable list as a counter. cumbersome, but it gets the job done. would there be a more efficient way of doing this?
Answer
Aha! Fun problem. Took me a while to get a better solution than what you have. Your solution looks good, but you’re right that it will be bigger than 3n/2 for numbers that aren’t close to a power of two.
You can do this instead:
Keep a record of the current smallest and largest number. If n is odd, set the first number to be biggest and smallest. If n is even, compare indexes 0 and 1 and mark the bigger as biggest and the smaller as smallest.
Compare the next pair of numbers to each other. Compare the smaller to the current smallest and the larger to the current largest. Note that this takes exactly 3 comparisons.
Continue doing this across the array. Bam! 3n/2 exactly! Or one or two comparisons cheaper if n is even.
P.S. Since this is an algorithms question, I would be remiss in pointing out that a naïve solution is still O(n), just as these are. So fun optimizations but not interesting from a complexity perspective.