基础原理

本板块整理自灵茶山艾府b站视频二分查找 红蓝染色法_哔哩哔哩_bilibili

通过一道例题进行讲解：

例题

返回数组中第一个≥8\geq 8 数字的位置，如果所有数都<8< 8 则返回长度值

非常明显这道题我们可以采用二分查找的方法来解决，首先我们先讲解一下闭区间二分解决这道题的写法：

闭区间二分写法

假设队列长度为m，首先设左指针L指向0，右指针指向m-1。每次取中间的元素进行判断，如果中间的元素≥8\geq 8 则 R= mid-1否则L = mid+1，持续更新直到L>R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
vector<int> arr = {5,7,7,8,8,10};
int main(){
    int len = arr.size();
    int l = 0, r = len-1;
    while(l<=r){
        int mid = l+(r-l)/2;
        if (arr[mid]>=8) r = mid-1;
        else l = mid+1;
    }
    cout<<l;
    return 0;
}

注意：二分中求mid的写法，像上面这样写能有效的避免

这里其实就可以感觉到，在更新的过程中，无论何时L-1指向的一定是<8的数R+1指向的一定是>=8的数

左闭右开二分写法

这个是经常看到的二分的写法

同样假设队列长度为m，左指针L指向0，右指针指向m，每次取中间元素进行判断，如果中间元素≥8\geq 8则R = mid，否则L = mid+1，持续更新直到 L≥RL\geq R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
vector<int> arr = {5,7,7,8,8,10};
int main() {
    int len = arr.size();
    int l = 0, r = len;
    while(l<r){
        int mid = l+(r-l)/2;
        if(arr[mid] >= 8) r = mid;
        else l = mid+1;
    }
    cout<< l;
    return 0;
}

开区间二分写法

同样假设队列长度为m，左指针指向-1，右指针指向m，每次取中间元素进行判断，如果中间元素≥8\geq 8则R = mid, 否则L = mid，持续更新直到L+1≥RL+1 \geq R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
vector<int> arr = {5,7,7,8,8,10};
int main() {
    int len = arr.size();
    int l = -1, r = len;
    while(l+1<r){
        int mid = l + (r-l)/2;
        if (mid>=8) r = mid;
        else l = mid;
    }
    cout << r;
    return 0;
}

一道例题

题目传送门：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

其中找当前数出现的最后一个，就是找比他大1的数的第一个位置，然后把这个位置-1。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        int l = 0, r = len;
        while(l<r){
            int mid = l+(r-l)/2;
            if (nums[mid]>=target) r=mid;
            else l = mid+1;
        }
        
        if (l == len || nums[l]!=target){
            vector<int> nw = {-1,-1};
            return nw;
        }
        vector<int> ans;
        ans.emplace_back(l);
        l = 0; r = len;
        while(l<r){
            int mid= l+(r-l)/2;
            if(nums[mid]>=target+1) r=mid;
            else l = mid+1;
        }
        ans.emplace_back(l-1);
        return ans;
    }
};

当然这道题使用lower_bound和upper_bound也是可以的，具体使用方法见C++部分。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto it = lower_bound(nums.begin(),nums.end(),target);
        if (it == nums.end() || *it != target) return vector<int>{-1,-1};
        auto it2 = upper_bound(nums.begin(), nums.end(), target);
        return vector<int>{int(it-nums.begin()),int(it2-nums.begin())-1};
    }
};

总结

可能看完上面的几种写法，还是没有理解二分的本质是什么，这里就来总结一下。其实通过观察上面常见的三种写法我们不难发现，二分的目的是判断整个区间和一个目标值的大小关系，为了达到这个目的，我们需要牢记区间的定义！区间内的数（下标）都是还未确定与 target 的大小关系的，有的是 < target，有的是 ≥ target；区间外的数（下标）都是确定与 target 的大小关系的。

理解了上述定义，则二分查找算法也就理解了。

二分题单（右边数字为难度分）

二分答案

  1. H 指数 II
  2. 使结果不超过阈值的最小除数 1542
  3. 完成旅途的最少时间 1641
  4. 每个小孩最多能分到多少糖果 1646
  5. 准时到达的列车最小时速 1676
  6. 在 D 天内送达包裹的能力 1725
  7. 爱吃香蕉的珂珂 1766
  8. 可移除字符的最大数目 1913
  9. 制作 m 束花所需的最少天数 1946
  10. 可以到达的最远建筑 1962
  11. 最大合金数 1981
  12. 逃离火灾 2347

275. H指数

题目传送门：275. H 指数 II - 力扣（LeetCode）

二分判定条件就是如果当前citation数量仍然大于等于后面的文章数量就还可以往前二分。需要注意的是要判断一下数组有没有越界。

左闭右开二分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int len = citations.size();
        int l = 0,r = len;
        function<bool(int)> judge = [&](int x){
            if (citations[x]>=len-x) return true;
            else return false;
        };
        while(l < r){
            int mid = l+(r-l)/2;
            if (judge(mid)) r = mid;
            else l = mid+1;
        }
        return l==len?0:min(len-l,citations[l]);
    }
};

1283. 使结果不超过阈值的最小除数

题目传送门：1283. 使结果不超过阈值的最小除数 - 力扣（LeetCode）

一道非常明显的二分题目，需要注意的是是上取整，这点有点坑。

开区间二分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        function<bool(int)> judge = [&](int x){
            int ans = 0;
            for (auto &num:nums) { 
                if (num%x) ans = ans+num/x+1;
                else ans += num/x;
            }
            return ans<=threshold;
        };
        int l=0,r=1000001;
        while (l+1<r) {
            int mid = l+(r-l)/2;
            if (judge(mid)) r=mid;
            else l=mid;
        }
        return r;
    }
};

2187. 完成旅途的最少时间

题目传送门：2187. 完成旅途的最少时间 - 力扣（LeetCode）

闭区间二分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long r = 100000000000003;
        long long l = 0;
        function<bool(long long)> judge=[&](long long x){
            long long ans = 0;
            for (auto tim:time) {
                ans += x / tim;
            }
            return ans>=(long long)totalTrips?true:false;
        };
        while (l <= r) {
            long long mid = l + (r - l)/2;
            if (judge(mid)) r = mid-1;
            else l = mid+1;
        }
        return l;
    }
};

2226. 每个小孩最多能分到多少糖果

题目传送门：2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）

闭区间二分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        auto maxit = max_element(candies.begin(),candies.end());
        int max_ele = *maxit;
        function<bool(long long)> judge = [&](int x) {
            long long ans = 0;
            if (x==0) return true;
            for (auto candy:candies) {
                ans += candy/x;
            }
            return ans>=k?true:false;
        };

        int l=0,r=max_ele;
        while (l<=r) {
            int mid = l + (r-l)/2;
            if(judge(mid)) l=mid+1;
            else r=mid-1;
        }
        return r;
    }
};

1870. 准时到达的列车最小时速

题目传送门：1870. 准时到达的列车最小时速 - 力扣（LeetCode）

左闭右开区间二分如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int len = dist.size();
        function<bool(int)> judge = [&](int v) {
            int time=0;
            for(int i=0;i<len-1;++i) {
                time += dist[i]/v;
                if (dist[i]%v) time += 1; 
            }
            double fin_time = (double)time + (double) dist[len-1]/(double)v;
            return fin_time <= hour?true:false;
        };
        int l = 1,r = 10000001;
        while (l<r) {
            int mid = l + (r-l)/2;
            if(judge(mid)) r = mid;
            else l = mid+1;
        }
        return judge(l)?l:-1;
    }
};

注意：最后返回的时候要判断一下当前速度能不能按规定到达目的地

1011. 在 D 天内送达包裹的能力

题目传送门：1011. 在 D 天内送达包裹的能力 - 力扣（LeetCode）

左闭右开区间二分代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        function<bool(int)> judge = [&](int x){
            int cur=0,cur_day=1;
            for (auto weight:weights) {
                if(cur+weight <= x){
                    cur = cur+weight;
                } else {
                    cur_day++;
                    cur = weight;
                }
            }
            return cur_day<=days?true:false;
        };
        int l = *max_element(weights.begin(), weights.end());
        int r = accumulate(weights.begin(),weights.end(),0)+1;
        while (l<r) {
            int mid = l + (r-l)/2;
            if (judge(mid)) r = mid;
            else l = mid+1;
        }
        return l;
    }
};

可以留意一下里面accumulate求和函数的用法

875. 爱吃香蕉的珂珂

875. 爱吃香蕉的珂珂 - 力扣（LeetCode）

开区间二分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        function<bool(int)> judge = [&](int v){
            long long cos = 0;
            for(auto pile:piles){
                cos += pile/v;
                if(pile%v) cos += 1;
            }
            return cos<=(long long)h?true:false;
        };
        int l = 0,r = INT_MAX;
        while (l+1<r) {
            int mid = l + (r-l)/2;
            if(judge(mid)) r = mid;
            else l = mid;
        }
        return r;
    }
};

1898. 可移除字符的最大数目

题目传送门：1898. 可移除字符的最大数目 - 力扣（LeetCode）

同样首先观察数据范围，1e5的数据范围，预感这道题应该使用二分。

这道题比之前的题目要稍微难一点，难点主要集中在judge函数的书写上，其实只要在每次判断时使用一个哈希数组记录一下当前字符有没有被删除，就可以较为简单的解决这道题。以下提供两种开区间二分写法，注意区分其中细节，如果能够区分出来差别，那恭喜，说明你很好的掌握了的二分查找🎇。

二分下标（判断到当前下标之前（包含当前下标）能否被remove）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int len = s.size();
        function<bool(int)> judge=[&](int x){
            vector<bool> vis(len,true);
            for (int i=0;i<=x;++i) vis[removable[i]] = false;
            int pp = 0;
            for(int i=0;i<len;++i){
                if (s[i]==p[pp]&&vis[i]){
                    pp++;
                    if (pp == p.size()) return true;
                }
            }
            return false;
        };
        int l = -1, r = removable.size();
        while (l+1<r) {
            int mid = l + (r-l)/2;
            if (judge(mid)) l = mid;
            else r = mid;
        }
        return l+1;
    }
};

二分前n个remove的这个n：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int len = s.size();
        function<bool(int)> judge=[&](int x){
            vector<bool> vis(len,true);
            for (int i=0;i<x;++i) vis[removable[i]] = false;
            int pp = 0;
            for(int i=0;i<len;++i){
                if (s[i]==p[pp]&&vis[i]){
                    pp++;
                    if (pp == p.size()) return true;
                }
            }
            return false;
        };
        int l = -1, r = removable.size()+1;
        while (l+1<r) {
            int mid = l + (r-l)/2;
            if (judge(mid)) l = mid;
            else r = mid;
        }
        return l;
    }
};

1482. 制作 m 束花所需的最少天数

题目传送门：1482. 制作 m 束花所需的最少天数 - 力扣（LeetCode）

同样首先观察数据范围，1e5的数据范围，预感这道题应该使用二分。

同上，就是需要设计一下judge函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
         auto judge = [&](int x) {
             int cnt=0,cur=0;
             for (auto bloom:bloomDay) {
                 if (bloom <= x) {
                    cur++;
                    if (cur == k) {
                        cur = 0;
                        cnt ++;
                        if (cnt == m) return true; 
                    }
                 }
                 else cur = 0;
             }
             return false;
         };
        int l = 1, r = *max_element(bloomDay.begin(),bloomDay.end());
        while (l <= r) {
            int mid = l + (r-l)/2;
            if (judge(mid)) r=mid-1;
            else l=mid+1;
        }
        return judge(l)?l:-1;
    }
};

1642. 可以到达的最远建筑

题目传送门：1642. 可以到达的最远建筑 - 力扣（LeetCode）

同样首先观察数据范围，1e5的数据范围，预感这道题应该使用二分。

左闭右开区间二分写法如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        auto judge = [&](int x) { 
            vector<int> h_diffs;
            for(int i=1;i<=x;++i){
                if (heights[i] > heights[i-1]) h_diffs.emplace_back(heights[i]-heights[i-1]);
            }
            if (ladders>=h_diffs.size()) return true;
            sort(h_diffs.begin(),h_diffs.end());
            int sum_diff = accumulate(h_diffs.begin(),h_diffs.end()-ladders,0);
            return sum_diff <= bricks?true:false;
        };
        int l=0,r=heights.size();
        while(l<r){
            int mid = l + (r-l)/2;
            if (judge(mid)) l = mid+1;
            else r=mid;
        }
        return l-1;
    }
};

注意：该题合法区间在左边，所以最终左闭右开区间二分返回值应该是l-1

2861. 最大合金数

题目传送门：2861. 最大合金数 - 力扣（LeetCode）

题目中规定只能使用一个机器生产所有合金，所以就非常简单了，和之前的二分差不多，只不过中间计算开销的时候会爆int所以设置成long long。

左开右闭二分书写如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        auto judge = [&](int x) {
            for(int i=0; i<k; ++i) {
                long long  cost_all = 0;
                for(int j=0; j<n; ++j) {
                    cost_all += max((long long)0, ((long long)x*composition[i][j]-stock[j]))*cost[j]; 
                    if(cost_all > budget) break;
                } 
                if (cost_all <= budget) return true;
            } 
            return false;
        };
        int l = 0, r = INT_MAX;
        while (l<r) {
            int mid = l + (r-l)/2;
            if(judge(mid)) l = mid+1;
            else r = mid;
        }
        return l-1;
    }
};

2258. 逃离火灾

这道题还是非常有意思的，是一道bfs和二分的结合，首先我们先使用bfs预处理一遍将每个格子着火的时间都先处理出来。然后我们使用二分，二分等待时间，二分判断函数就是第二次bfs，判断在当前等待时间下能否进入安全屋。所以一共需要提供两个bfs函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    int maximumMinutes(vector<vector<int>>& grid) {
        vector<vector<int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        int n = grid.size(),m = grid[0].size();
        vector<vector<int>> tim_burn(n,vector<int>(m,INT_MAX));

        auto judge = [&](int x,int y) {
            if (x<0||y<0||x>=n||y>=m) return false;
            if (grid[x][y] == 2) return false;
            return true;
        };
        auto bfs1 = [&](int x, int y){
            
        };
        
        auto bfs2 = [&](int stay_time){
            vector<vector<int>> reach(n,vector<int>(m,INT_MAX));
            if (stay_time > tim_burn[0][0]) return false;
            queue<vector<int>> que;
            que.push(vector<int>{0,0});
            reach[0][0] = stay_time;
            while (!que.empty()) {
                vector<int> nw = que.front();que.pop();
                for(auto dir:dirs) {
                    if (judge(nw[0]+dir[0],nw[1]+dir[1])) {
                        int nx = nw[0]+dir[0], ny = nw[1]+dir[1];
                        if (nx == n-1 && ny == m-1 && tim_burn[nx][ny] >= reach[nw[0]][nw[1]]+1) return true;
                        if (tim_burn[nx][ny] > reach[nw[0]][nw[1]]+1) {
                            if (reach[nx][ny] > reach[nw[0]][nw[1]]+1){
                                reach[nx][ny] = reach[nw[0]][nw[1]]+1;
                                que.push(vector<int>{nx,ny});
                            }   
                        }
                    }
                }
            }
            return false;
        };
        queue<vector<int>> que1;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if (grid[i][j]==1) {
                    tim_burn[i][j] = 0;
                    que1.push(vector<int>{i,j});
                }
            }
        }        
        while (!que1.empty()) {
            vector<int> nw = que1.front();que1.pop();
            for(auto dir:dirs) {
                if (judge(nw[0]+dir[0],nw[1]+dir[1])) {
                    int nx = nw[0]+dir[0], ny = nw[1]+dir[1];
                    if (tim_burn[nx][ny] > tim_burn[nw[0]][nw[1]]+1) {
                        tim_burn[nx][ny] = tim_burn[nw[0]][nw[1]]+1;
                        que1.push(vector<int>{nx,ny});
                    }
                }
            }
        }
        // close interval
        int l = 0, r = 1000000000;
        while(l <= r) {
            int mid = l + (r-l)/2;
            if(bfs2(mid)) l = mid+1;
            else r = mid-1;
        }
        return bfs2(1000000000)?1000000000:l-1; 
    }
};
注意

第一次预处理的时候就将所有的火源都压入bfs队列中预处理一次就行了，不要每次发现一个火源就bfs一次，非常的浪费时间。

最小化最大值

  1. 分配给商店的最多商品的最小值 1886
  2. 袋子里最少数目的球 1940
  3. 最小化数组中的最大值 1965
  4. 打家劫舍 IV 2081
  5. 水位上升的泳池中游泳 2097
  6. 最小化数对的最大差值 2155
  7. 最小化两个数组中的最大值 2302

最大化最小值

  1. 两球之间的磁力 1920
  2. 最大合金数 1981
  3. 礼盒的最大甜蜜度 2021
  4. 找出最安全路径 2154
  5. 最大化城市的最小供电站数目 2236

本站由 @anonymity 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。