struct Solution {}

impl Solution {
  pub fn find_radius(houses: Vec<i32>, heaters: Vec<i32>) -> i32 {
    let mut houses = houses;
    let mut heaters = heaters;
    houses.sort();
    heaters.sort();
    let mut s = heaters.binary_search(&houses[0]).unwrap_or_else(|x| x);
    let l = heaters.len();
    let mut ret = 0;
    for h in houses {
      while s + 1 < l && h >= heaters[s + 1] {
        s += 1;
      }  
      if h <= heaters[0] {
        ret = ret.max(heaters[0] - h);
      } else if s == l - 1 {
        ret = ret.max(h - heaters[l - 1])
      } else {
        ret = ret.max((h - heaters[s]).min(heaters[s + 1] - h));
      }
    }
    ret
 }
}