二分查找

可以二分的前提：有序

时间复杂度：O(log n)

模板

目前只遇到了两种二分情况，基本可以包括所有二分的情景：

  1. 前半段是false，后半段是true，查找最靠左的true

    形如：false false false false true true true

    实例：对于升序数组，查找第一个大于等于target的元素的下标

    1
    2
    3
    4
    5
    6
    7
    8
    int l = 0, r = n - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(nums[mid] >= target)
        	r = mid - 1;
        else l = mid + 1;
    }
    return l;

  2. 前半段是true，后半段是false，查找最靠右的true

    形如：true true true false false

    实例：对于降序数组，查找最后一个大于等于target的元素的下标

    1
    2
    3
    4
    5
    6
    7
    8
    int l = 0, r = n - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(nums[mid] >= target)
        	l = mid + 1;
        else r = mid - 1;
    }
    return r;

    例题：34. 在排序数组中查找元素的第一个和最后一个位置

while判断条件始终是小于等于，l和r始终是mid往右/往左一步。需要最靠哪边的true，就返回哪边的指针，即靠左对应return l；靠右对应return r；在不确定返回l还是r时，可以举例子，模拟一下l和r最终的指向。

二分答案

对于求极小值的极大值问题，通常可以转化为在有序数组中求最靠左/最靠右的true的问题，进而可以转化为二分查找问题。

例题：1760. 袋子里最少数目的球

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

  • 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有正整数个球。
    • 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例 1：

1
2
3
4
5
6
输入：nums = [9], maxOperations = 2
输出：3
解释：
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

分析：随着开销的增大，操作数ops会减小，因此对开销进行二分，找到满足ops <= maxOperations的最小开销，即最靠左的true。可以想象一个数组以开销为索引，其值前半段是false，后半段是true。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int l = 1, r = *max_element(nums.begin(), nums.end());
        while(l <= r){
            int mid = (l + r) / 2;
            int sum = 0;
            for(auto& num: nums)
                sum += (num - 1) / mid;

            if(sum <= maxOperations)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
};

__END__