Closest arithmetic progression to an array
Let's call your array $a$. The goal is to find $x,k$ such that $\sum|a_i-(ix+k)|$ is minimized. Fix $x$ and replace $a_i$ by $b_i=a_i-ix$. Now the goal is to minimize $\sum|b_i-k|$, so $k$ is obviously the median of $b$. Since it's not hard to solve this problem with fixed $x$, it's natural to consider if there's any monotonicity on $x$.

Note that the error can be written as $\sum_{b_i\in upper\,half}b_i-\sum_{b_i\in lower\,half} b_i$. Substitute $b_i$ by $a_i-ix$ and we'll get a formula like $c-(\sum_{b_i\in upper}i-\sum_{b_i\in lower}i)x$, which is linear. The optimal $x$ can be found trivially in this case, but the order of $b$ changes when $x$ incerases (decreases). Let's see how it changes. 

Scan $x$ from negative to positive. At some points a "swap" may happen: originally $b_i&lt;b_j$ but after this point $b_i&gt;b_j$. This only happens when $i&lt;j$. If they are originally in the same half then nothing happens. But if originally $i$ is in the lower half and $j$ is in the upper half, now $i$ moves to the upper half and $j$ moves to the lower half. This increases the slope by $2(j-i)$. Median should be excluded from both halves if $N$ is odd but the conclusion "slope is increasing" remains.

Now we know the error is a convex function so we can find the minimum by ternary search on $x$. Since we can compute the error in $O(N)$ if we fix $x$ and the range of $x$ is bounded by $O(M)$, the total complexity  is $O(N \log M)$. (Here I consider the cost of each arithmetic operation as a constant.)