二分算法自我总结与反思(上)

一.二分查找

1.含义：二分查找（Binary Search）是一种高效的查找算法，核心是每次将查找范围减半，仅适用于已排序的数组或区间，时间复杂度为O(log n)。

2.操作过程：以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值，只需要到左侧查找。

3.前提：有序

注：当中间位置的数不是我们所查找的数时，注意接下来应该往那边找

4.以下是基础二分查找代码示例：

int bs(vector<int>& a, int n, int target) { int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (a[mid] == target) { return mid;//无重复目标值时 } else if (a[mid] > target) { r = mid - 1; } else { l = mid + 1; } } return -1; }

二.二分答案---猜答案（二分查找的应用）

1.做题步骤：确定题目是二分的题目->确定答案的范围->假定一个解判断是否可行

2.题目类型：最值问题（可能要用二分，例题https://www.luogu.com.cn/problem/P1873和https://leetcode.cn/problems/nZZqjQ/） 最小化最大值以及最大化最小值问题（大概率用二分）

3.例题1.https://www.luogu.com.cn/problem/P1873

根据题目可以知道：给定n棵树的高度，求一个最大的参数值h，使他把所有树h以上的部分砍掉以后，能得到m米或者以上的木材。换句话说，如果再升高 1 米，他将得不到 M 米木材。

那我们可以二分树的高度0-400000，然后在check函数中去判断是否可行，即算一下得到的木材是否满足m。

以下是例题代码：

#include<iostream> #include<limits> #include<algorithm> #include<vector> #define neg_inf LLONG_MIN #define inf LLONG_MAX #define int long long using namespace std; int check(int mid,vector<int>&a,int m) { int sum = 0; int n = a.size(); for (int i = 0; i < n; i++) { if (a[i]> mid) {//如果当前的树的高度大于高度h，那么就可以加入当前sum sum += a[i] - mid; } } if (sum >= m) { return 1; } else { return 0; } } void solve() { int n, m; cin >> n >> m; vector<int>h(n); for (int i = 0; i < n; i++) { cin >> h[i]; } int l = 0, r = 400000,ans=-1; while (l <= r) {//二分 高度h范围0--400000 int mid = (l + r) / 2; if (check(mid, h, m)) {//检查是否大于等于m l = mid + 1;//如果成立那么继续向右查找 ans = mid; } else { r = mid - 1;//如果不成立那么就向左查找 } } cout << ans << endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; } 

4.例题2https://leetcode.cn/problems/nZZqjQ/：

我们二分吃香蕉的速度，然后去以这个速度为标准吃香蕉头。使用一个judge判断这个解是不是可行解。 由于每小时都要吃香蕉，即每小时至少吃 1个香蕉，因此二分查找的下界是 1；由于每小时最多吃一堆香蕉，即每小时吃的香蕉数目不会超过最多的一堆中的香蕉数目，因此二分查找的上界是最多的一堆中的香蕉数目。 这个judge怎么实现呢？用每堆香蕉的个数除以速度，得到吃完该堆香蕉的时间。然后把每堆时间相加（t）和h比较，如果t<=h,说明速度还可以更小，调整上界。否则说明速度太慢了，需要变大，调整下界。

以下是例题代码：

#include<iostream> #include<limits> #include<algorithm> #include<vector> #define neg_inf LLONG_MIN #define inf LLONG_MAX #define int long long using namespace std; bool check(vector<int>& piles, int h,int k) { int t=0; int n = piles.size(); for (int i = 0; i < n; i++) { t += piles[i] / k; if (piles[i] % k != 0) { t++; } } if (t <= h) { return 1; } else { return 0; } } int minEatingSpeed(vector<int>& piles, int h) { int l = 1, r = 0; int n = piles.size(); for (int i = 0; i < n; i++) { r = max(piles[i], r); } int ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(piles, h,mid)) { r = mid - 1; ans = mid; } else { l = mid + 1; } } return ans; } void solve() { int n, h; cin >> n >> h; vector<int>p(n); for (int i = 0; i < n; i++) { cin >> p[i]; } int k = minEatingSpeed(p, h); cout << k << endl; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; }