The median of the $v_i$ minimizes this function, so you should sort the $v_i$ and pick the middle value, which takes $O(n\log n)$ time.
If $n$ is even, pick any value between the middle two elements (it is easy to see that changing $v_p \rightarrow v_p + \delta v_p$ doesn't change $c$ unless $v_p$ crosses one of the $v_i$.)
Edit:
A binary search would find an optimal value in $O(\log n)$ function evaluations, each of which executes in $O(n)$ time, for a total running time of $O(n\log n)$.
If you follow my advice and sort the $v_i$ to find the median, it will take $O(n\log n)$ comparisons on average. However, you can be smarter: using a selection algorithm it is possible to compute the sample median in $O(n)$ time, and this is a lower bound on the complexity.