基本框架

二分查找的思維確實非常簡單 就是引入一個猜炸彈編號的問題 相信大家玩過對吧 假如炸彈是0-100中間的一個數字 不會玩的人可能一個一個猜 會玩的人一般上來就猜50 25 …

二分查找代碼中的細節很重要但是真正的坑根本就不是那個細節問題，而是在于到底要給 mid 加一還是減一，while 里到底用 <= 還是 <，

這就要分別對應兩種寫法 ：
一種是左閉右閉區間 一種是左閉右開區間 講解視頻我附在這里：
代碼隨想錄的詳細講解

labuladong 算法筆記 :

整數查找（序列二分的模版題 建議先做）

題目鏈接

滿分代碼及思路

首先題目其實說的非常直白就是根據給的flag（1 2 3 4 ）分別對應四種不同的查詢方案 那么我們的main函數就分別對于這四種情況 分別調用函數返回結果即可

做完你再看 序列二分的本質上 是不是 在有限的一個區間或者序列中 快速找到滿足條件的數

solution

#include <iostream>
using namespace std;
int n, q;
const int N = 1e5 + 9;
int a[N]; // 存一下序列A
int flag; // 取決于我們該怎么去查找
int l, r, x;
int ans;// 輸出 A[l～r] 中等于 x 最左邊的數的下標，若不存在輸出 -1
void search1(int l, int r, int x) {ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if (a[mid] == x) {ans = mid;r = mid - 1;} else if (a[mid] < x) {l = mid + 1;} else {r = mid - 1;}}
}// 輸出 A[l～r] 中等于 x 最右邊的數的下標，若不存在輸出 -1
void search2(int l, int r, int x) {ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if (a[mid] == x) {ans = mid;l = mid + 1;} else if (a[mid] < x) {l = mid + 1;} else {r = mid - 1;}}
}// 輸出 A[l～r] 中大于等于 x 的第一個數的下標，若不存在輸出 -1
void search3(int l, int r, int x) {ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if (a[mid] >= x) {ans = mid;r = mid - 1;} else {l = mid + 1;}}
}// 輸出 A[l～r] 中大于 x 的第一個數的下標，若不存在輸出 -1
void search4(int l, int r, int x) {ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if (a[mid] > x) {ans = mid;r = mid - 1;} else {l = mid + 1;}}
}int main() {cin >> n >> q;for (int i = 1; i <= n; i++) {cin >> a[i];}while (q--) {cin >> flag >> l >> r >> x;if (flag == 1) {search1(l , r , x);} else if (flag == 2) {search2(l , r , x);} else if (flag == 3) {search3(l , r , x);} else if (flag == 4) {search4(l , r , x);}cout << ans << endl;}return 0;
}    

子串簡寫

題目鏈接

滿分代碼及思路

solution 1（暴力 模擬雙指針70分）

對于這道題目其實我首先想到的就是雙指針，具體拿這題來說就是，我們現在有兩個指針left right 現在要做的就是 在給定的字符串中枚舉出所有同時滿足：

1.長度大于等于K；
2.以c1開頭以c2結尾

以上兩個條件的所有子串 對吧
那么就很好辦了呀 我們先讓left指針找到c1，然后通過不斷移動right
枚舉出所有以left此時位置為左端點 且滿足條件的所有合法情況 每次更新答案count 就好 最后輸出一下
但是有幾個比較大的樣例超時了 這時候我們就需要想辦法優化一下：

因為我們這個雙指針的方法 主要依靠兩個for循環 時間復雜度是O(n*n)

Q:所以我們要思考的是我們可以去優化的點在哪啊？

也就是說這個代碼有什么重復且不必要的操作嗎？

我覺得這個思考很重要很重要

A:二分相對于雙指針優化的點是不是在于c2位置的確定啊 因為雙指針需要枚舉right每一種情況吧 因為我們就像一個瞎子 我們的right只有走到它的兒子面前才能跟他相認

具體來說，在雙指針方法里，對于每一個以 c1 開頭的位置，代碼需要從 left + K - 1 開始，逐個枚舉所有可能的 right 位置，直到找到以 c2 結尾的位置，從而判斷是否滿足子串長度大于等于 K 的條件

二分查找方法首先記錄下所有 c1 和 c2 出現的位置。對于每一個 c1 出現的位置，要尋找滿足子串長度大于等于 K 的 c2 位置時，它利用 c2 位置數組的有序性（因為位置是按順序記錄的）進行二分查找
此時我們的right指針他是一個視力很好的人 他知道自己的子女 在這條路的哪個方位

二分查找每次將搜索范圍縮小一半，其時間復雜度為 (O(log m))，其中 m 是 c2 出現的次數。對于所有 c1 出現的位置都進行二分查找，整體時間復雜度就是 (O(n log m))，在一般情況下可以近似看作 (O(n log n))，相比于雙指針方法的 (O(n^2)) 有了顯著的優化。

#include <iostream>
#include <string>// 引入標準庫命名空間
using namespace std;// 雙指針方法
int double_point(int K, const string& S, char c1, char c2) {int n = S.length();int count = 0;for (int left = 0; left < n; ++left) {if (S[left] == c1) {for (int right = left + K - 1; right < n; ++right) {if (S[right] == c2) {++count;}}}}return count;
}int main() {int K;string S;char c1, char c2;// 讀取輸入cin >> K;cin >> S >> c1 >> c2;// 計算結果int result = double_point(K, S, c1, c2);// 輸出結果cout << "雙指針方法結果: " << result << endl;return 0;
}

solution 2（二分 AC）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>using namespace std;// 二分查找方法
int binary_search(int K, const string& S, char c1, char c2) {int n = S.length();vector<int> start;vector<int> end;// 記錄 c1 和 c2 出現的位置for (int i = 0; i < n; ++i) {if (S[i] == c1) {start.push_back(i);}if (S[i] == c2) {end.push_back(i);}}int count = 0;for (int s : start) {// 二分查找滿足條件的 c2 位置int left = 0, right = end.size() - 1;int target = s + K - 1;while (left <= right) {int mid = left + (right - left) / 2;if (end[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}count += end.size() - left;}return count;
}int main() {int K;string S;char c1, c2;// 讀取輸入cin >> K;cin >> S >> c1 >> c2;// 計算結果int result = binary_search(K, S, c1, c2);// 輸出結果cout << "二分查找方法結果: " << result << endl;return 0;
}    

管道

題目鏈接

滿分代碼及思路

代碼和思路參考：視頻講解
BZW ：這是我偶然刷到的一個up 真的很優秀很有思維

樣例解釋與思路分析

對于這道題目首先我們需要搞清楚 我們要干嘛
可以將這個管道看成一條線段 閥門就是線段上的點
我們需要明確的是這個閥門只要一打開就會向左右兩邊同時灌水 就可以看成是以這個點為中心向左右兩邊延伸 length的長度
并且 len與時間t的函數是一個單調遞增函數

solution

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,len;
const int N=1e5+10;
int a[N][2];//存儲輸入每個閥門的位置和時間
struct door{int L;//位置int S;//時刻
}d[N];
struct line{int l;int r;
}w[N];
//sort比較函數 從小到大排左端點 如果一樣就把右端點大的放后面
bool cmp(line A,line B)
{if(A.l!=B.l){return A.l<B.l;}else{return A.r<B.r;}}
bool check(int x)
{int cnt=0;for(int i=0;i<n;i++)//生成區間{if(x<d[i].S)continue;w[cnt].l=d[i].L-(x-d[i].S);w[cnt].r=d[i].L+(x-d[i].S);cnt++;}sort(w,w+cnt,cmp);int last=0;//線段合并for(int i=0;i<cnt;i++){//為什么是last+1 因為題目把這些管道看作是一個個離散的點 所以只要我們新區間的右端點>last+1(l=臨界情況)//就return falseif(w[i].l>last+1){return false;}last=max(w[i].r,last);}if(last<len){return false;}return true;
}
int main()
{cin>>n>>len;for(int i=0;i<n;i++){cin>>d[i].L>>d[i].S;}//讀入完成int mid=0;int l=0;int r=2e9;//最壞的情況就是從1ee9開始流 直到2e9才能鋪滿管道//二分答案 左閉右開寫法while(l<r){mid=(l+r)/2;if(check(mid))//如果mid這個時間能鋪滿整個管道 說明在mid右邊的時刻都是合法的//那么我們就需要操作：//不減1是因為我們不能保證mid是不是臨界點 也就是我們不知道mid-1是什么情況{r=mid;}else{l=mid+1;}}cout<<l<<endl;return 0;
}

最大通過數

題目鏈接

滿分代碼及思路

solution 1（貪心 50分）

// 我們現在需要做的就是用這K個水晶 通過盡可能多的關卡 并且我們不需要關心水晶的分配問題
// 也就是說兩個人共享一個背包 首先在闖關之前 我肯定想要比較一下左右兩個入口 
// 優先通過消耗水晶小的關卡 這樣才能保證 最好通過關卡的數量最多
#include <iostream>
using namespace std;
const int N = 2e5 + 9;
int a[N], b[N]; // 分別表示左右兩邊關卡的能源數量
int n, m, k;    // 初始狀態下有n+m道關卡 一共有K個水晶
int passCount;void work() {int i = 0, j = 0;// 先處理左右兩邊都有的關卡while (i < n && j < m) {if (a[i] <= b[j] && k >= a[i]) {passCount++;k -= a[i];i++;} else if (k >= b[j]) {passCount++;k -= b[j];j++;} else {break;}}// 處理左邊剩余的關卡while (i < n && k >= a[i]) {passCount++;k -= a[i];i++;}// 處理右邊剩余的關卡while (j < m && k >= b[j]) {passCount++;k -= b[j];j++;}
}int main() {cin >> n >> m >> k;for (int i = 0; i < n; i++) {cin >> a[i];}for (int j = 0; j < m; j++) {cin >> b[j];}work();cout << passCount;return 0;
}

問題

solution 2（二分 AC）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 2e5 + 4;
ll a[N], b[N], pre_a[N], pre_b[N];
ll n, m, k;// 檢查是否可以通過 mid 個關卡
bool check(ll mid) {bool ok = false;  // 記錄 mid 關卡數是否有可行的方案，不關心 a,b 各通過幾關// 從關卡數少的人開始枚舉(mid > max(m,n) 時)for (ll i = 0; i <= min(min(m, n), mid); ++i) {// 保證另外一個人有足夠的關卡數來湊為 mid 關，沒有就跳過if (mid - i > max(m, n)) continue;// 從關卡數少的人開始枚舉(保證不越界)if (m <= n && pre_b[i] + pre_a[mid - i] <= k) {ok = true;} else if (n < m && pre_a[i] + pre_b[mid - i] <= k) {ok = true;}}return ok;
}// 解決問題的函數
void solve() {cin >> n >> m >> k;// 讀取左邊入口每個關卡所需的寶石數for (int i = 1; i <= n; ++i) {cin >> a[i];}// 讀取右邊入口每個關卡所需的寶石數for (int i = 1; i <= m; ++i) {cin >> b[i];}// 計算 a[i] 前綴和，代表 a 通過 i 關所需的寶石for (int i = 1; i <= n; ++i) {pre_a[i] = pre_a[i - 1] + a[i];}// 計算 b[i] 前綴和，代表 b 通過 i 關所需的寶石for (int i = 1; i <= m; ++i) {pre_b[i] = pre_b[i - 1] + b[i];}// 二分查找最大通過的關卡數ll l = 0, r = m + n + 10;while (l + 1 != r) {ll mid = (l + r) >> 1;if (check(mid)) {l = mid;  // mid 可行，說明 mid 可能可以更大，更新 l} else {r = mid;}}cout << l;  // l 為答案
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--) {solve();}return 0;
}