> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/binary-search/774.-minimize-max-distance-to-gas-station.md).

# 774. Minimize Max Distance to Gas Station

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:**

1. `stations.length` will be an integer in range `[10, 2000]`.
2. `stations[i]` will be an integer in range `[0, 10^8]`.
3. `K` will be an integer in range `[1, 10^6]`.
4. Answers within `10^-6` of the true value will be accepted as correct.

```cpp
// Binary Search
double minmaxGasDist(vector<int>& stations, int K) { // time: O(n * log(stations[n - 1] - stations[0])); space: O(1)
    int n = stations.size();
    double low = 0, high = stations.back() - stations.front();
    while (low + 1e-6 < high) {
        double mid = (low + high) / 2.0;
        int count = 0;
        for (int i = 0; i < n - 1; ++i) {
            count += ceil((stations[i + 1] - stations[i]) / mid) - 1;
        }
        if (count > K) low = mid;
        else high = mid;
    }
    return low;
}
```