算法题分类记录二分法篇

Hoshea Zhang2023-11-152023-11-22

有些解题方法其实很常规但是一直做不好，准备专题做一些题目，这一轮做二分法专题

这篇博客用于记录这个专题的学习

简介

以在一个升序数组中查找一个数为例，每次考察当前数组的中间部分，如果刚好是要找的，那就结束搜索过程，如果中间元素小于所查找的值，那么左侧更小，只需要右侧查找，反之只需要去左侧查找。

二分查找

在一个已知的有序数据集上进行二分查找
二分答案

答案有一个区间，在这个区间中二分，直到找到最优答案

二分查找

前提条件：数组有序

待查数组需有序，搜索区间两端闭；
while 条件带等号，否则补丁打不及。
if 相等便返回，其他杂事可不提；
mid 必须加减一，因为区间两端闭。
while 结束就GG，凄凄惨惨返-1；
如果元素有重复，相等返回需注意。

最简单的二分查找

搜索一个数，存在返回索引不存在返回-1

int check(vector<int>& num,int t){
    int left = 0;
    int right = num.size()-1;
    while(left<=right){
        int mid = (right-left)/2+left;
        if(num[mid]<t){
            left = mid+1;
        }
        else if(num[mid]>t){
            right = mid-1;
        }
        else return mid;
    }
    return -1;
}

寻找左侧边界的二分查找

初始化right = size

因此左开右闭

因此right = mid而不是mid-1

int check(int num[],int size,int t){
    int left=0,right=size;
    while(left<right){  			//每次循环的查找区间是[left,right)左闭右开
        int mid=(left+right)/2;
   		if(nums[mid]<t){
            left=mid+1;
        }else if(nums[mid]>t){
            right=mid; 
        }else{					  //两个条件可以合并为一个 
        	right=mid;
		}
    }
    return left;			//终止的条件是left==right，此时搜索区间[left,left)为空，可以正确终止
}

def lower_bound(nums, target):
    low, high = 0, len(nums) - 1
    pos = len(nums)
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1      # 和模版有所区别的是，这里对两种情况进行了一个合并
    return low

寻找右侧边界的二分查找

我们还是用左开右闭的方法，要寻找右侧边界那么，找到t时不能立即返回，需要收紧左侧，收紧左侧那么当找到值的时候应该使left = mid+1，最后的结果时left-1

int check(int num[],int size,int t){
    int left=0,right=size;
    while(left<right){			//每次循环的查找区间是[left, right)
        int mid=(left+right)/2;
        if(num[mid]<t){
            left=mid+1;
        }else if(nums[mid]>target){
            right=mid;
        }else{					//两个条件可以合并为一个
            left=mid+1; 
        }
    }
    return left-1; 				//终止的条件是left==right，此时搜索区间(right,right]为空，可以正确终止
}

def upper_bound(nums, target):
    low, high = 0, len(nums) - 1
    pos = len(nums)
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] > target:
            high = mid - 1
        else:
            low = mid + 1       # 和模版有所区别的是，这里对两种情况进行了一个合并
    return high + 1             # 要大于才行，所以要加一

二分答案

某个问题的答案是一个区间，对这个区间进行二分，找到最好的答案

例题

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

样例
输入：
1
2
3
4
5
6
25 5 2
2
11
14
17
21
输出：
1
4
将与起点距离为 2和 14的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

解答

#include<cstdio>
using namespace std;
 
const int N=50005;
int d[N];
int main(){
	int L,n,m,ans,x,left,right,mid;
	
	scanf("%d%d%d",&L,&n,&m);
	
	for(int i=0;i<n;i++){
		scanf("%d",&d[i]);
	}
	
	left=0;right=L;
	
	while(left<=right){
		mid=(left+right)/2;
		ans=0;
		x=0;
		d[n]=L;
		for(int i=0;i<=n;i++){
			if(d[i]-x<mid){
				ans++;				//两石头间距离小于mid，mid不是最短距离，不满足，移走该石头
			}else{
				x=d[i];				//符合，跳过去
			} 
		}
		if(ans<=m){
			left=mid+1;				//要的是距离的最大，所以尽可能地往右走
		}else{
			right=mid-1;
		}
	}
	printf("%d",left-1);
	return 0;
}

11.16

875爱吃香蕉的柯柯

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：

1 2	输入：piles = [3,6,7,11], h = 8 输出：4

解答

class Solution {
public:
    int timeuse(vector<int>& piles, int k){
        int res = 0;
        for(auto i:piles){
            if(i%k==0){
                res+=i/k;
            }
            else res+=i/k+1;
        }
        return res;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        sort(piles.begin(),piles.end());
        int l = 1;
        int r = piles[piles.size()-1];
        while(l<r){
            int mid = (r-l)/2+l;
            if(timeuse(piles,mid)>h){
                l = mid+1;
            }
            if(timeuse(piles,mid)<=h){
                r = mid;
            }
        }
        return r;
        
    }
};

11.22

209长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解答

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        const int n = nums.size();
        vector<int> preSum(n + 1, 0);
        for(int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + nums[i - 1];

        int ans = INT_MAX;
        for(int i = 0; i < n; i++){
            int t = target + preSum[i];
            int l = i, r = n;
            while(l <= r){
                int mid = l + ((r - l) >> 1);
                if(preSum[mid] < t) l = mid + 1;
                else r = mid - 1;
            }

            if(l <= n) ans = min(ans, l - i);
        }
        return ans == INT_MAX ? 0 : ans;
    }
};