Explaining the math behind an algorithm

Question

Given a sorted array of integers a, find such an integer x that the value of

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x) is the smallest possible (here abs denotes the absolute value). If there are several possible answers, output the smallest one.

Example

For a = [2, 4, 7], the output should be absoluteValuesSumMinimization(a) = 4.

I was able to solve this by brute forcing it but then i came upon this

function absoluteValuesSumMinimization(A) {
    return A[Math.ceil(A.length/2)-1];
}

looking to learn how/why this works.

Answer 1

Let's break it down.

A.length/2 returns half the length, used to find the middle of the array. For even-length arrays, this will be to the right of the middle. For odd-length arrays, it'll be the middle.

Math.ceil(A.length/2) rounds up if necessary, so the middle of an array of 5 would be 2.5 -> 3. This makes the odd-length arrays off by one.

Math.ceil(A.length/2)-1 goes down one index. This corrects off-by-one errors for all the arrays.

All this solution is saying is that in an array of even length, the value you're looking for will always be to the left of the middle. In an array of odd length, it will always be the middle item.

This makes sense intuitively. Subtracting the middle item in the array from each item will always result in the lowest sum. In an even length array, the two center items will always result in an identical sum, so the lowest number will be to the left of the center.

To see this, remove the console.log comment from this brute-force solution and try several arrays:

function absoluteValuesSumMinimization(ints) {
  const vals = [];

  ints.forEach(int => {
    const sum = ints.reduce((accum, next) => {
      return accum + Math.abs(next  - int);
    }, 0);

    vals.push(sum);
  });

  // console.log(vals);
  const lowest = Math.min(...vals);
  return ints[vals.indexOf(lowest)];
}