Formatted question description: https://leetcode.ca/all/774.html

# 774. Minimize Max Distance to Gas Station

## Level

Hard

## Description

On a horizontal number line, we have gas stations at positions `stations[0], stations[1], ..., stations[N-1]`

, where `N = stations.length`

.

Now, we add `K`

more gas stations so that **D**, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of **D**.

**Example:**

**Input:** stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9

**Output:** 0.500000

**Note:**

`stations.length`

will be an integer in range`[10, 2000]`

.`stations[i]`

will be an integer in range`[0, 10^8]`

.`K`

will be an integer in range`[1, 10^6]`

.- Answers within
`10^-6`

of the true value will be accepted as correct.

## Solution

Use binary search. Sort `stations`

and initialize `low`

to 0 and `high`

to the difference between the maximum element in `stations`

and the minimum element in `stations`

. While `high - low > 1e-6`

, do binary search. Each time set `mid`

to be the average of `low`

and `high`

and use `mid`

as a candidate of **D** to calculate the minimum number of gas stations to be added. If the minimum number of gas stations to be added is less than or equal to `K`

, then set `high = mid`

. Otherwise, set `low = mid`

. Finally, return `low`

.

```
class Solution {
public double minmaxGasDist(int[] stations, int K) {
Arrays.sort(stations);
int length = stations.length;
double low = 0, high = stations[length - 1] - stations[0];
while (high - low > 1e-6) {
double mid = (low + high) / 2;
int minStations = 0;
for (int i = 1; i < length; i++)
minStations += (int) ((stations[i] - stations[i - 1]) / mid);
if (minStations <= K)
high = mid;
else
low = mid;
}
return low;
}
}
```