一、475. Heaters
输入: [1,2,3],[2] 输出: 1 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。 输入: [1,2,3,4],[1,4] 输出: 1 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
1.思路：（1）先对heaters数组进行排序（2）对于每个house，计算其在heaters中的位置（3）计算这个house到其左和右heater的距离的最小值，也就是说heater只管离自己最近的house。（4）然后，取这些最小值的最大值即可。
houses = [1,2,3,4], heaters = [1,4]
house = 1：0-0,3-0，最小值：0，1在heaters中 ，index为0，dist1=MAX_VALUE，dist2=heaters[0]-1=0,result = 0
house = 2：1-0,3-1，最小值：1，2不在heaters中，index为-2，修正为1，dist1 = 2-heaters[0] = 1,dist2 = heaters[1]-2=2,result = 1
house = 3：2-0,3-2，最小值：1，3不在heaters中，index为-2，修正为1，dist1 = 3-heaters[0] = 2,dist2 = heaters[1]-3=1,result = 1
house = 4：3-0,3-3，最小值：0，4在heaters中 ，index为1，dist1 = 4-heaters[0] = 3,dist2 = heaters[1]-4=0,result = 0
2.代码：需要注意的点：if (index < 0) index = -(index + 1);，这是因为如果house没有出现在heaters中，返回的是-（low+1），看上面↑
public int findRadius(int[] houses, int[] heaters) { Arrays.sort(heaters); int result = Integer.MIN_VALUE; for (int house : houses) { int index = Arrays.binarySearch(heaters, house); if (index < 0) index = -(index + 1); int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE; int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE; result = Math.max(result, Math.min(dist1, dist2)); } return result; }
二、69. Sqrt(x)
输入: 4 输出: 2 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
1.思路：由于当mid*mid <= x < (mid+1) * (mid+1)时，返回的结果是mid，又由于根号下x小于等于二分之x，所以右边界可以设为x/2，使用二分法寻找即可。
2.代码：以x = 33,为例，left=1，right=16，mid=8，mid*mid>x，left=1，right=7，mid=4，mid*mid<33，(mid+1)(mid+1)<33，left=5，right=7，mid=6，mid*mid>33,
left=5,right=6,mid=5,mid*mid<x,(mid+1)(mid+1)>33,return mid=5.
需要注意的地方：（1）while (true)条件（2）使用mid > x/mid而不用mid*mid是为了避免出现overFlow的问题。
public int mySqrt(int x) { if (x == 0) return 0; int left = 1, right = x/2; while (true) { int mid = left + (right - left)/2; if (mid > x/mid) { right = mid - 1; } else { if (mid + 1 > x/(mid + 1)) return mid; left = mid + 1; } } }
三、