Why this is still binary search on the answer
The shipping-capacity version establishes the pattern: you cannot construct the optimum directly, but you can test a candidate cheaply, and the test is monotone. That page owns the invariant and the minimise-the-maximum direction. This one is the mirror, and the mirror is where candidates who memorised the first loop come unstuck.
Here the candidate is a gap d, and the test is "can I place all m sensors so that every adjacent pair is at least d apart?" Construction looks like a search over subsets of positions. Checking one gap is a single pass. So you search the range of gaps, not the array of positions, and each probe costs O(n).
The cue in the wording is "maximise the minimum". Placing routers along a street, spacing out stalls, picking m items so the closest two are far apart: every one has a numeric answer, a cheap check and a predicate that runs in one direction.
The greedy check, and why it is enough
Sort the positions first. Unlike the shipping problem, where the order was fixed and part of the input, the order here is meaningless, and the greedy pass relies on walking left to right.
Put the first sensor at the smallest position. Then take each position in turn and place a sensor there if it is at least d from the last one placed. If you reach m sensors, d is feasible.
The justification is an exchange argument. Take any valid placement for gap d. Its first sensor can move to the leftmost position without shrinking any gap, because moving it left only widens the gap to its neighbour. By induction, the greedy's i-th sensor is never to the right of the optimal placement's i-th sensor, so greedy always has at least as many positions left to use. If any placement fits m sensors, greedy fits m too.
Monotonicity then needs one line. A placement whose gaps are all at least d also has all gaps at least d - 1. So the predicate reads true, true, true, then false forever, and you want the boundary from the left.
static boolean canPlace(int[] pos, int m, int gap) {
int placed = 1, last = pos[0];
for (int i = 1; i < pos.length && placed < m; i++) {
if (pos[i] - last >= gap) { placed++; last = pos[i]; }
}
return placed >= m;
}
static int largestMinGap(int[] positions, int m) {
int[] pos = positions.clone();
Arrays.sort(pos);
int lo = 1;
int hi = (pos[pos.length - 1] - pos[0]) / (m - 1);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPlace(pos, m, mid)) lo = mid;
else hi = mid - ;
}
lo;
}
The bounds are facts, not guesses. With distinct positions and m no larger than n, a gap of 1 is always achievable, so lo is feasible. The m − 1 gaps between consecutive sensors add up to at most the span, so the smallest gap cannot exceed the span divided by m − 1. Using the whole span as hi would also be correct. It costs about log2(m − 1) extra iterations and nothing else.
Trace it on positions [1, 2, 3, 4, 7] with m = 3. The range starts at [1, 3]. The midpoint 2 is feasible (1, 3, 7), so lo becomes 2. The next midpoint is 3, also feasible (1, 4, 7), so lo becomes 3 and the loop ends. The answer is 3.
The floor midpoint that hangs the mirrored loop
The failure here is carrying the shipping loop across unchanged. That loop uses a floor midpoint because its keeping branch is hi = mid. Floor never equals hi when lo < hi, so the range always shrinks.
In this problem the keeping branch is lo = mid, and floor rounding breaks it. Take the trace above at the point where the range is [2, 3]. A floor midpoint is 2, which is feasible, so lo = mid sets lo to 2 again. The range never shrinks and the loop spins. The ceiling midpoint, lo + (hi - lo + 1) / 2, gives 3 instead, and progress is guaranteed.
Every binary search on the answer obeys the same rule from the neighbouring page: floor pairs with hi = mid, ceiling pairs with lo = mid. What is new is having to say which direction the predicate runs before writing either line. A strong candidate states "true then false, I want the last true" first, and the assignments follow. A weaker one writes the familiar loop, gets an infinite loop or an off-by-one, and starts swapping < for <=.
If you would rather keep one loop shape in your head, search for the first infeasible gap with the original floor template and return one less than it. That is equally correct, as long as your hi is itself infeasible, which means starting it one above the span bound.
Cost
Sorting costs O(n log n). Each feasibility check is O(n), and the search makes about log R checks, where R is the width of the gap range. The total is O(n log n + n log R) time and O(n) space for the sorted copy. As with every binary search on the answer, the logarithm is over the size of the answer, not over n. Positions near a billion still need only about thirty checks.
Before writing the loop, say which side of the boundary you want. "Last true" means lo = mid and a ceiling midpoint; everything else follows from that sentence.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).