774. Minimize Max Distance to Gas Station

-
https://www.lintcode.com/problem/minimize-max-distance-to-gas-station/
https://leetcode.com/problems/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.
---
Related problems
---
Intuition
Corner cases =>
    Worst case => Input 1 station at 0, K = 1 => Place new station furthest away at 10 ^ 8 => hi = 1e8
    Best case => Input 2 stations at 0, 2 * 1e -6 => Place new station at mid ~ 1e -6 => lo = 1e-6

Any placement which reduces distance below 1e -6 is invalid

Perform binary search between lo and hi

  • Terminate loop till search space is in bounds = > hi - lo >= 1e-6
  • Save result if valid, and continue searching in left half
  • Use hi = mid, lo = mid during sample walkthrough. 
  • Code works with hi = mid - 1e-6, lo = mid + 1e-6
  • isValid function
    • TODO
---
Time - O(N Log (Search Space) ) => O( N Log 1e 8 / 1e -6)) => O(N Log 1e14) => O(N) 
Space - O(1)
---