模版 - 二分

两类模版

• 参考

二分模板一共有两个，分别适用于不同情况。

• 模板1和模板2本质上是根据代码来区分的，而不是应用场景:
  • 如果写完之后发现是l = mid，那么在计算mid时需要加上1
  • 否则如果写完之后发现是 r = mid，那么在计算mid时不能加1

总结 -> 解决最大最小问题

• 先判断想要拿到什么 -> 写出isTrue()函数
• isTrue(mid) -> 接着判断是更新l = mid，还是更新r = mid
  • 这里的判断就与列表True分区有关系，需要仔细思考一下
• 最终返回的索引为：范围内使isTrue成立的，“最小的”值
  • 注意这里最小为：其它使条件的值均“大于”该值

算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，计算mid时不需要加1

int bsearch_1(int l, int r)
{
    while (l < r)
    {
	    // 这里加法可能会有溢出风险 -> l + ((r-l) >> 1)
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid，此时为了防止死循环，计算mid时需要加1

int bsearch_2(int l, int r)
{
    while (l < r)
    {
	    // same l + ((r - l + 1) >> 1)
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

版本3 -> 全开区间写法

• 这种方法确实也挺不错的 👍👍👍
• 红蓝染色：分为左右，主要看👀需要的在左边👈，还是在右边👉
  • 根据需要在if分支更新l或者r
• 需要的在左边，那么l就是答案
• 需要的在右边，那么r就是答案
• 结束时：l + 1 == r
  如何确定check函数呢？
• 我要找的元素应该满足什么性质？
• mid满足什么性质时
  • 一定被染成蓝色
  • 一定被染成红色

    int bsearch_3(int l, int r)
    {
    	while (l + 1 < r)
    	{
    		int mid = l + ((r - l) >> 1);
    		// 根据具体的逻辑选择更新l，还是r:
    		// 需要的在左边则更新 l；否则更新r
    		// 需要意味着：check == true
    		if (check(mid)) r = mid;
    		else l = mid;
    	}
    	return r;
    }
    
    vector<int>vec = {9, 7, 6, 5, 1, 0, 0, -1, -3, -4};
    
    // 找到第一个 >= 0 的数的下标
    int bsearch1(vector<int>& nums)
    {
    	int l = -1, r = nums.size();
    	while (l + 1 < r)
    	{
    
    		int mid = l + ((r - l) >> 1);
    		if (nums[mid] >= 0) l = mid;
    		else r = mid;
    	}
    	return l;
    }
    
    int bsearch2(vector<int>& nums)
    {
    	int l = -1, r = nums.size();
    	while (l + 1 < r)
    	{
    
    		int mid = l + ((r - l) >> 1);
    		if (nums[mid] < 0) r = mid;
    		else l = mid;
    	}
    	return r-1; // return l;
    }

例题

2560. 打家劫舍 IV

• 这个的二分解法很抽象 -> 需要理解二分最本质的原理
• 先用版本1/2的思路写一下；之后在看灵神的视频
  • 这题比较关键的一个点：

答疑

问：有没有可能，二分出来的答案，不在 nums 中？

答：不可能。二分出来的答案，一定在 nums 中。证明如下：

设答案为 ans，那么当最大金额为 ans 时，可以偷至少 k 间房子。如果 ans 不在 nums 中，那么当最大金额为 ans−1 时，也可以偷至少 k 间房子。这与二分算法相矛盾：根据视频中讲的红蓝染色法，循环结束时，ans 和 ans−1 的颜色必然是不同的，即 ans 可以满足题目要求，而 ans−1 不满足题目要求。所以，二分出来的答案，一定在 nums 中。

162. 寻找峰值

• 局部最大值

评估最大工作量

「题目描述」：其团队以来了一个大项目，该项目己知有n个需求，每个需求工作量分别需要有t1、t2…tn人天。每个需求要么不做，要么全部完成，必须耗时ti人天完成。现在小梁想知道T人天的预算最多能做多少人天的需求。
「数据范围」：1<=n<=40;1<=ti<=10^9 ; 1<= T<=10^9
「思路」：由于ti，T的值都很大，直接01背包会超时；所以先计算出所有可能的耗时，找到<=T的第一个值，即为最终答案
「优化」：考虑进一步降低所有可能耗时数目，采用拆分的方式：

lefts,rights = [],[]  
// 计算左半边所有可能
bktc(0,arr[:n//2],0,lefts)  
bktc(0,arr[n//2:],0,rights)  
rights.sort()  
res = 0  
for i,l in enumerate(lefts):  
    #找到 <= T-l的最大值  
    index = bisect.bisect_right(rights, T-l)  
    if index:  
       res = max(res, l + rights[index-1])  
  
print(res)