One-dimensional k-center problem. Finding minimum distance

Question

This is a follow-up to this question: Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

Which algorithm should i use to get minimal possible value of $d(X,Y)$?

I tried do develop dynamic programming algorithm but didn't succeed. In my previous question i was told that this problem is known as unweighted one-dimensional k-center problem. I've looked through some papers on the net but all of them offered the ways to find some particular $Y$. But my current problem seems to be easier: i need only the optimal value of $d(X,Y)$. So i expect the solution to be rather standard and rather easy.

Thanks in advance.

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

Answer 1

Hint: Turn the problem upside down and ask yourself: can I easily check if the answer is less than or equal to $t$?

• Igor: Unforunately i don't understand how this helps with original problem. Could you please elaborate a bit more on this?
• Mihai: If you know how to answer this question, you can do a binary search on the answer.
• Igor: Isn't binary search in such situation applicable only when answer is integer? I can have rational number.
• Mihai: Well no, why would it? In this problem you're required to output only two digits after the decimal point, you're not supposed to output a fraction (even then, sometimes you can binary search for fractions!).