class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int len_min = Integer.MIN_VALUE;

        Arrays.sort(heaters);

        for (int i = 0; i < houses.length ;i++) {
            int pos_house = houses[i];
            find_closest_left_right_pos(pos_house, heaters, 0, heaters.length - 1);

            Integer radius_shorter = null;
            if (pos_heater_left != null && pos_heater_right != null) {
                int radius_heater_left = Math.abs(pos_house - pos_heater_left);
                int radius_heater_right = Math.abs(pos_heater_right - pos_house);
                radius_shorter = Math.min(radius_heater_left, radius_heater_right);  // pick nearer one
            }else if (pos_heater_left != null) {
                radius_shorter = Math.abs(pos_house - pos_heater_left);
            }else if (pos_heater_right != null) {
                radius_shorter = Math.abs(pos_heater_right - pos_house);
            }

            if (radius_shorter != null) {
                len_min = Math.max(len_min, radius_shorter); // attention: this is max - the lowest requirement
            }

        }


        return len_min;
    }

    Integer pos_heater_left = null;
    Integer pos_heater_right = null;
    public void find_closest_left_right_pos(int pos_house, int[] heaters, int i_left, int i_right) {
        if (i_left > i_right) return;

        int i_mid = (i_left + i_right) / 2;
        int pos_heater = heaters[i_mid];
        if (pos_house == pos_heater) {
            pos_heater_left = pos_heater;
            pos_heater_right = pos_heater;
        }else if (pos_house > pos_heater) {
            pos_heater_left = pos_heater;
            find_closest_left_right_pos(pos_house, heaters, i_mid + 1, i_right);
        }else if (pos_house < pos_heater) {
            pos_heater_right = pos_heater;
            find_closest_left_right_pos(pos_house, heaters, i_left, i_mid - 1);
        }

        return;
    }

}