// 考虑到所有情况的搜索
var findRadius2 = function (houses, heaters) {
  //  1. 取暖器和房子排序
  houses.sort((a, b) => {
    return a - b
  });
  heaters.sort((a, b) => {
    return a - b
  });
  let max = 0
  const minHeater = heaters[0];
  const maxHeater = heaters[heaters.length - 1];

  houses.forEach((house, houseIndex) => {
    let minRadis;
    if (heaters.length === 1) {
      let min = heaters[0];
      minRadis = Math.abs(house - min);
      max = Math.max(max, minRadis)
      return
    }
    if (house <= minHeater) {
      minRadis = minHeater - house
      max = Math.max(max, minRadis)
      return
    }
    if (house >= maxHeater) {
      minRadis = house - maxHeater
      max = Math.max(max, minRadis)
      return
    }
    else {
      // 在两个中间找到最符合的情况
      let midIndex = heaters.findIndex((heater, heaterIndex) => {
        const beyond = heater <= house;
        const below = house <= heaters[heaterIndex + 1];
        return beyond && below
      });
      minRadis = Math.min(house - heaters[midIndex], heaters[midIndex + 1] - house);
    }
    max = Math.max(max, minRadis)
  })
  console.log(max);
  return max
}

var findRadius3 = function (houses, heaters) {
  let ans = 0;
  heaters.sort((a, b) => a - b);
  for (const house of houses) {
    const i = binarySearch(heaters, house);
    const j = i + 1;
    const leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i];
    const rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;
    const curDistance = Math.min(leftDistance, rightDistance);
    ans = Math.max(ans, curDistance);
  }
  return ans;
};

const binarySearch = (nums, target) => {
  let left = 0, right = nums.length - 1;
  if (nums[left] > target) {
    return -1;
  }
  while (left < right) {
    const mid = Math.floor((right - left + 1) / 2) + left;
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid;
    }
  }
  return left;
}


var findRadius4 = function (houses, heaters) {
  houses.sort((a, b) => a - b);
  heaters.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0, j = 0; i < houses.length; i++) {
    let curDistance = Math.abs(houses[i] - heaters[j]);
    while (j < heaters.length - 1 && Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])) {
      j++;
      curDistance = Math.min(curDistance, Math.abs(houses[i] - heaters[j]));
    }
    ans = Math.max(ans, curDistance);
  }
  return ans;
};

findRadius2([1, 2, 3], [2])
findRadius([1, 5], [2])
findRadius2([1, 2, 3, 4], [1, 4]) //3
findRadius2([1, 5], [10]) //3
findRadius4(
  [474833169, 264817709, 998097157, 817129560],
  [197493099, 404280278, 893351816, 505795335]
)
Math.abs(houses[i] - heaters[j]) >= Math.abs(houses[i] - heaters[j + 1])
findRadius2(
  [282475249, 622650073, 984943658, 144108930, 470211272, 101027544, 457850878, 458777923],
  [823564440, 115438165, 784484492, 74243042, 114807987, 137522503, 441282327, 16531729, 823378840, 143542612])