How to create divide-and-conquer algorithm?

Question

I started to learn about divide-and-conquer algorithms in my data structures class and currently I having a problem with my homework. I have a given array/list of n integers and I need to find the element, for which sum of absolute values of differences of it and other's elements is the lowest. Something, that can be solved with brute-force algorithm similar to written-below one:

def return_sum(element, my_list):
sum_of_diff = 0
for number in my_list:
sum_of_diff += abs(number - element)
return sum_of_diff

some_list = [10, 4, 8]
sums = {elem: return_sum(elem, some_list) for elem in some_list} # {10: 8, 4: 10, 8: 6}

for key in sums:
if sums[key] is min(sums.values()):
print(key) # 8

I know that this code is terrible, but it's purpose was to make clear, what algorithm should do. The problem is that I have to write an optimal divide-and-conquer algorithm in recursive and iterative version. And I have no idea how to make it. I'll be gratefull if you could give me any hint, how to create proper algorithm.

Sincerely thanks for your help.

Answer 1

The value you are looking for is a median of the array. Now you need to build an algorithm for efficient finding of the median. It turns out that if we generalize the problem to finding the element that would be in the k-th place in a sorted array (k-th order statistics) it's easy to build a divide-and-conquer algorithm:

1) patition your list in two parts a1 and a2 of sizes n1 and n2 so that n1 and n2 are close to n/2 (strictly speaking you need there to be a constant c>0, such that 1-c >n1/n > c) , and each element of a1 is less than each element of a2.
2) if k < n1 you search for k-th element in a1, else search for (k-n1)-th element in a2.

You can do step 1 by selecting a random element (pivot) in the array and dividing that array into parts less than pivot, and larger than or equal to pivot. That will give you linear time on average. To get worst case linear time you need to use a better choice of pivot (for example a "median of medians" approach)