面试题72：
问题：
输入一个非负整数，计算它的平方根。
解决方案：
- 使用二分查找。一个数x的平方根一定小于或等于x，同时，除了0之外的所有非负整数的平方根都大于等于1，故该数的平方根在1到x的范围内。
- 定义left为1作为左边界，right为x作为右边界。取该范围内的中间数字m，并判断m是否小于x/m，如果m小于x/m，那么继续判断（m+1）是否大于x/（m+1），如果（m+1）大于x/（m+1），那么返回m，如果（m+1）不大于x/（m+1），那么目标值位于数组后半部分。如果m大于或等于x/m，那么目标值位于数组前半部分。
源代码：
class Solution {
public int mySqrt(int x) {
int left = 1;
int right = x;
while(left <= right){
int mid = (left + right)/2;
//
if(mid <= x/mid){
if(mid + 1 > x/(mid + 1)){
return mid;
}
left = mid + 1;
}else{
right = mid - 1;
}
}
return 0;
}
}
面试题73：
问题：
门卫走开H小时，有n堆香蕉，狒狒去吃香蕉，狒狒一个小时只能吃一堆香蕉，狒狒要在门卫回来前将香蕉吃完，问狒狒每个小时至少得吃多少根香蕉。
解决方案：
- 使用二分查找。狒狒吃香蕉的速度的范围在1和数组中的最大值（也就是n堆香蕉的最大值）记为max根。
- 在1-max中取中间值mid，求出按照每个小时吃mid根的速度吃完n堆香蕉需要多少小时记为time1，如果time1小于或等于H，那么继续判断mid是否为1，如果是，那么mid就是狒狒每小时吃香蕉速度的最小值。如果mid不为1，那么继续判断以mid-1求出的时间time2与H，如果time2大于H，那么mid就是狒狒每小时吃香蕉速度的最小值。如果time2小于H，那么狒狒吃香蕉的速度还可以慢点。如果time1大于H，那么狒狒吃香蕉的速度应该快些。
源代码：
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = Integer.MIN_VALUE;
for (int pile : piles) {
right = Math.max(right, pile);
}
while (left <= right) {
int mid = (left + right) / 2;
int midTime = getTime(piles, mid);
if (midTime <= h) {
if (mid == 1 || getTime(piles, mid - 1) > h) {
return mid;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
//计算狒狒每个小时吃mid根，所花费的时间
private int getTime(int[] piles, int mid) {
int time = 0;
for (int pile : piles) {
time += pile / mid;
if (pile % mid != 0) {
time++;
}
}
return time;
}
}
