Where do you place the chargers?

As EVs grow, charging lines get longer at every highway rest stop. Rest stops sit along a straight road, and budget lets you install chargers at only C of them. Where should they go?

Here's the catch: if chargers cluster in one area, far stretches become inconvenient. So the goal is to make the distance between the two closest chargers as large as possible.

Example: rest stops at 3, 6, 12, 17, 25, 30 (km), with 3 chargers. Answer: 13km. (Place at 3·17·30 → gaps 14, 13 → minimum 13.)

How do you approach this? (The core idea)

It feels hopeless at first. Choosing *which* stops directly makes the number of combinations explode.

Flip it — don't choose positions. Assume the answer (minimum distance D) first.

•"Can I place C chargers so that the minimum gap is at least D?" → this is a quick greedy check (always place at the first stop, then at every stop that is at least D away from the last placed one).
•Small D is easy (feasible); large D is hard (infeasible). So feasibility is monotonic in D.
•Monotonic? Then binary search finds the largest feasible D.

That's parametric search — *binary-searching the answer itself.* You're not searching values in a sorted array; you're narrowing the range of candidate answers.

Why is it confusing?

Most people learn "binary search = find a value in a sorted array." So *"binary-search the answer"* rarely comes to mind at first.

But once you see it, it clicks:

1. Pick a candidate distance D

2. Greedily place chargers from the front using D

3. If you placed enough, raise D; if not, lower it

4. The range narrows and converges to the answer

Following this as a step-by-step animation makes "*ah, that's* why it's binary search" land instantly.

See it with your own eyes

We built the entire process as a step-by-step visualization: rest stops on a number line, the candidate distance D narrowing, and chargers placed greedily one by one — with every variable (lo·mid·hi, placed count) visible.

👉 EV Charger Placement — watch the step-by-step visualization

Parametric search shows up in coding tests in countless disguises ("router setup", "cutting trees", "budget split"). Learn the principle visually once, and you can solve any variant.