作者：whisper

链接：http://proprogrammar.com:443/article/379

声明：请尊重原作者的劳动，如需转载请注明出处

    最近在做leetcode题的过程中多次用到了二分法，用到了分别获取high, low, mid值的方法，觉得应该写一篇文章记录一下。下面分别说一下。

    注：right, left; high, low; h, l都是一个意思，表示搜索的右端和左端（高端和低端），我以high, low, mid为例

    先分享一下原题

    33. 搜索旋转排序数组   要求的结果是mid

    5111. 分享巧克力    要求的结果是high

    475. 供暖器     要求的结果是low

    搜索旋转排序数组

    算法描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

    算法代码

    // 想法：用二分查找，数组分二段，两段分别递增，第一段值都比第二段大
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while(right >= left){
            mid = (right + left) / 2;
            if(nums[mid] > target){
                // 目标值，中间值都在第一段
                if(target >= nums[0]){
                    right = mid - 1;
                // 目标值在第二段，中间值在第一段
                }else if(nums[mid] >= nums[0]){
                    left = mid + 1;
                // 目标值，中间值都在第二段
                }else{
                    right = mid - 1;
                }
            }else if(nums[mid] < target){
                // 目标值，中间值都在第一段
                if(nums[mid] >= nums[0]){
                    left = mid + 1;
                // 目标值在第一段，中间值在第二段
                }else if(target >= nums[0]){
                    right = mid - 1;
                // 目标值，中间值都在第二段
                }else{
                    left = mid + 1;
                }
            }else{
                return mid;
            }
        }
        
        return -1;
    }

    算法说明

    算法要求的结果是数组中的一个数，所以正常情况下（这个数在数组中）会返回这个数的索引 mid（否则返回-1），这里是求数组中一个数的相关信息，而mid正是用来找这个数的，最后返回的也是mid，high, low, mid三者的判断、赋值情况是

判断

while(right >= left)

赋值

mid = (right + left) / 2

right = mid - 1;

left = mid + 1;

mid是要求的值，right, left左右端点值

    分享巧克力

    算法描述

你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。

为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。

请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。

示例 1：

输入：sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出：6
解释：你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

示例 2：

输入：sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出：1
解释：只有一种办法可以把巧克力分成 9 块。

示例 3：

输入：sweetness = [1,2,2,1,2,2,1,2,2], K = 2
输出：5
解释：你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。

提示：

• 0 <= K < sweetness.length <= 10^4
• 1 <= sweetness[i] <= 10^5

    算法代码

    // 二分法缩小范围
    public int maximizeSweetness(int[] sweetness, int K) {
        int low = 0, high = (int)1e9, mid, cont, temp;
        
        while(low < high) {
            // 二分法的一种取mid的方式
        	mid = (low + high + 1) / 2;
        	cont = 0;
        	temp = 0;
        	for(int i: sweetness) {
        		temp += i;
        		if(temp >= mid) {
        			temp = 0;
        			cont++;
        		}
        	}
        	
            // low值是满足条件的值
        	if(cont >= K + 1) {
        		low = mid;
        	}else {
        		high = mid - 1;
        	}
        }
        
        return low;
    }

    算法说明

    所要求值在high，low之间，不同切法都有总甜度，我们要求的是总甜度的最大值（最优解），怎么求呢，令满足要求的总甜度为low（开始最小，即要求最大，先设为最小，然后慢慢增大），然后慢慢增大low，直到不满足条件，从而得到满足条件的最大的low，high, low, mid三者的判断、赋值情况是

判断

while(low < high)

赋值

mid = (low + high + 1) / 2

high = mid - 1

low = mid

low是满足条件可能的值，mid是中间值，high右端值

     供暖器

    算法描述

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。

所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明:

• 给出的房屋和供暖器的数目是非负数且不会超过 25000。
• 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
• 只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
• 所有供暖器都遵循你的半径标准，加热的半径也一样。

示例 1:

输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:

输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

    算法代码

    // 想法：先确定半径范围，再不断缩小范围
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
    	Arrays.sort(heaters);
        // t为满足供暖的房屋数量(前t个房屋)
        int mid, t, l = 0, h = Math.max(houses[houses.length - 1] - heaters[0], heaters[heaters.length - 1] - houses[0]);
        
        loop: 
        while(h > l){
            mid = (h + l - 1) / 2;
            t = 0;
            for(int ht: heaters){
                // 满足供暖的前t个房间小于所有房间（不是所有房间都满足供暖）
                while(t < houses.length){
                    // 第t+1个房间满足供暖
                    if(ht + mid >= houses[t] && ht - mid <= houses[t]){
                        t++;
                    }else{
                        break;
                    }
                }
                
                // 所有房间都满足供暖，说明当前的mid（半径）满足，使h=mid
                if(t == houses.length){
                    h = mid;
                    continue loop;
                }

            }
            
            // 当前mid(半径)不满足条件，增大mid（半径）
            l = mid + 1;
        }

        return h;
    }

    算法说明

    所求值在h, l之间，我们要求的是半径的最小值（最优解），怎么求呢，令满足要求的半径为h（开始为最大，即要求最小，先设为最大，然后慢慢减小），然后慢慢减小h，直到不满足条件，从而得到满足条件的最小h，high, low, mid三者判断、赋值的情况是

判断

while(h > l)

赋值

mid = (h + l - 1) / 2

h = mid

l = mid + 1

h是满足要求的可能值，mid是中间值，l是左端值

亲爱的读者：有时间可以点赞评论一下