一、二分查找

1. 【案例】在排序數組中查找元素的第一個和最后一個位置 ?

【題目鏈接】

34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）

(1) 二分查找的引入

我們先來觀察以下這個題目，顯然，我們可以使用暴力解法去求解，即遍歷數組每一個元素。但是這樣的時間復雜度是 $O(n)$，有沒有更快的方法？答案是有的。暴力解法顯然沒有用到數組有序這樣的特點，而通過觀察我們可以發現，但當我們選中一個元素的時，我們會發現這個元素左邊的元素都是小于這個數的，而右邊的元素都是大于這個數的，因此我們就將數組劃分為了兩段。當我們任意查找一個值 x 時如果發現它小于 target，那么我們就可以直接把 x 左邊的區間所有數全部舍去，轉而去右邊的區間尋找 target。

此時我們說這個數組具有 二段性。如果有二段性，我們就可以使用二分查找算法去解決這個問題，時間復雜度為 $O(\log n)$。二分算法的大致思路是：

1. 定義一個 left 和 right，讓 left = 0（數組開頭），right = n - 1（數組結尾）。
2. 求出 left 和 right 的中點位置 mid，用 mid 指向的值與 target 作比較。
3. 如果 a[mid] < target，則讓 left 移動到 mid 的位置，反之讓 right 移動到 mid 的位置。
4. 重復 2、3 過程直到 left 和 right 相遇。

雖然有了大致的思路，但是落實到代碼上是有很多細節問題的，我們逐個來突破。

---

(2) 解題細節（important）

• left 和 right 如何移動？

當我們要查找 target 第一個出現的位置的時候，下面兩種寫法那種是正確的：

// 寫法一：
if(nums[mid] < target) left = mid + 1;
else right = mid;// 寫法二：
if(nums[mid] <= target) left = mid;
else right = mid - 1;

顯然寫法一是正確的。因為當 nums[mid] < target 的時候說面 mid 左邊的區間（包括 mid）都不是我們想要的元素，因為 left 可以放心移動到 mid 的后一位。如果 nums[mid] >= target 的話，有可能 mid 所指的元素就是我們要查找的元素，因此 right 只能移動到 mid 的位置。

而如果我們想要查找的是元素最后一個出現的位置時，則采用寫法二。

結論：查找第一個位置用寫法一，查找最后一個位置用寫法二。

---

• 求中點的方式如何選擇？

求數組中的中間位置，也就是 mid，有兩種方式：

int mid = (left + right) / 2;
int mid = (left + right + 1) / 2;

這兩種方式對于數組元素個數為奇數時沒有差別，但是數組元素個數是偶數的時候二者會有所不同。比如對于 [1, 2, 3, 4] 這樣的數組而言，使用第一種方式求出的 mid 在 2 的位置（中間靠左），用第二種方式求的 mid 在 3 的位置（中間靠右）。

而當我們需要查找元素的第一個位置時，需要采用第一種方式。例如當數組是 [2, 2] 時，采用第二種方式求出的 mid 會在第二個 2 的位置處，這樣的話 right 永遠不會移動，會陷入死循環。

但是當我們需要查找最后一個位置時，則需要采用第二種方式。因為根據上面提到的 left 和 right 的移動方式可知，如果用第一種方式求中點，對于 [2, 2] 這種情況會陷入死循環。

還需要注意的是，當數據范圍較大時，我們直接使用 left + right 這種寫法可能會超出數據類型的范圍。因此我們可以對它進行優化：

int mid = left + (right - left) / 2;
int mid = left + (right - left + 1) / 2;

這樣寫和上面兩種寫法效果一樣，并且不會有超范圍的風險。

結論：查找第一個位置用第一種方式，查找最后一個位置用第二種方式。

---

• 循環里的判斷條件怎么寫？

上面我們說到二分查找的結束條件是直到 left 和 right 相遇。那么 while 循環內的條件應該是 left < right 還是 left <= right 呢？思考一下，如果是 left <= right，那么面臨數組是 [2, 2]，而我想要查找的元素是第一個 2 的情況，那么這個循環將永遠不會結束！因為此時求出的中點在第一個 2 上，然后 right = mid，接著求中點，然后會發現 left 和 right 就不會動了，但是循環不會結束。因此循環的結束條件應是 left < right。查找最后一個位置同理可以說明當使用 left <= right 時會陷入死循環。

結論：循環條件都用 while(left < right)。

---

(3) 代碼示例

class Solution 
{
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty()) return {-1, -1};// 查找第一個位置int left = 0, right = nums.size() - 1;int ret1, ret2;while(left < right)  // 二分查找{int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}ret1 = nums[left] == target ? left : -1;  // 注意判斷找到的元素是否是我們想要的// 查找最后一個位置left = 0, right = nums.size() - 1;while(left < right)  // 二分查找{int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}ret2 = nums[left] == target ? left : -1;return {ret1, ret2};}
};

---

(4) 【模板】二分查找

通過上面的案例，我們可以總結出以下兩個模板。

// ?分查找區間左端點 int l = 0, r = n - 1;
// int l = 1, r = n;
while(l < r)
{int mid = l + (r - l) / 2;if(check(mid)) r = mid;else l = mid + 1;
}// ?分結束之后可能需要判斷是否存在結果

// ?分查找區間右端點 int l = 1, r = n;
// int l = 1, r = n;
while(l < r)
{int mid = l + (r - l + 1) / 2;if(check(mid)) l = mid;else r = mid - 1;  // 小技巧：出現減 1，那么求 mid 時就加 1
}// ?分結束之后可能需要判斷是否存在結果

【說明】

1. 不要死記硬背，算法原理搞清楚之后，在分析題目的時候自然而然就知道要怎么寫二分的代碼；
2. 僅需記住一點，if/else 中出現 ?1 的時候，求 mid 時 +1 就夠了。

---

(5) STL 中的二分查找

在 algotithm 算法庫中，有兩個寫好的二分查找算法。

1. lower_bound ：查找大于等于 x 的最小元素，返回的是迭代器；時間復雜度：$O(\log n)$。
2. upper_bound ：查找大于 x 的最小元素，返回的是迭代器。時間復雜度：$O(\log n)$。 二者均采用二分實現。但是 STL 中的二分查找只能適用于 “在有序的數組中查找”，如果是二分答案就不能使用。因此還是需要記憶二分模板。

---

2. 牛可樂和封印魔法 ??

【題目鏈接】

牛可樂和魔法封印

---

(1) 解題思路

這道題其實就是案例那道題套了一個情景，本質是一模一樣的。 唯一需要注意的是我們需要多考慮一下無效的情況。

當我們用二分查找找到大于等于 x 的第一個元素位置 left_num ，和小于等于 y 的第一個元素 right_num 時：

• 如果 left_num == 0，說明此時所有元素均小于 x，結果需要輸出 0。
• 如果 right_num == 0，說明此時所有元素均大于 y，結果需要輸出 0。

---

(2) 代碼實現

#include<iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;
LL a[N];
int n, q;int lower_bound(LL target)
{int left = 1, right = n;while(left < right){int mid = left + (right - left) / 2;if(a[mid] < target) left = mid + 1;else right = mid;}if(a[left] < target) return 0;  // 如果所有元素都小于 x, 那么返回 0return left;
}int upper_bound(LL target)
{int left = 1, right = n;while(left < right){int mid = left + (right - left + 1) / 2;if(a[mid] <= target) left = mid;else right = mid - 1;}if(a[left] > target) return 0;  // 如果所有元素都大于 y, 那么返回 0return left;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];cin >> q;while(q--){LL x, y;cin >> x >> y;int left_num = lower_bound(x);int right_num = upper_bound(y);if(left_num == 0 || right_num == 0) cout << 0 << endl;else cout << right_num - left_num + 1 << endl;}return 0;
}

---

3. A-B 數對 ?

【題目鏈接】

P1102 A-B 數對 - 洛谷

【題目描述】

給出一串正整數數列以及一個正整數 $C$，要求計算出所有滿足 $A?B=C$ 的數對的個數（不同位置的數字一樣的數對算不同的數對）。

【輸入格式】

輸入共兩行。

第一行，兩個正整數 $N,C$。

第二行，$N$ 個正整數，作為要求處理的那串數。

【輸出格式】

一行，表示該串正整數中包含的滿足 $A?B=C$ 的數對的個數。

【示例一】

輸入

4 1
1 1 2 3

輸出

3

【說明/提示】

對于 $75\%$ 的數據，$1\le N\le 2000$。

對于 $100\%$ 的數據，$1\le N\le 2\times 10^5$，$0\le a_i<2^{30}$，$1\le C<2^{30}$。

2017/4/29 新添數據兩組

---

(1) 解題思路

題目給定 C，讓我們尋找 A 和 B，那么我們可以枚舉 A，然后去尋找符合要求的 B，即尋找 A - C 的個數。

如何快速尋找 A - C 的個數？我們可以使用哈希表，這是最優的解法。但是同樣我們也可以使用二分查找去尋找。

1. 先將數組排序。
2. 利用二分查找尋找到大于等于 B 的第一個位置 left 和大于 B 的第一個位置 right。
3. 用 right - left 即可求出 B 的個數。

在二分查找時我們可以使用庫中的 lower_bound 和 upper_bound 函數，分別查找 left 和 right。

---

(2) 代碼實現

#include<iostream>
#include<algorithm>using namespace std;typedef long long LL;const int N = 2e5 + 10;
LL a[N];
LL n, c;int main()
{cin >> n >> c;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);LL cnt = 0;for(int i = 1; i <= n; i++){LL b = a[i] - c;auto left = lower_bound(a + 1, a + i, b);auto right = upper_bound(a + 1, a + i, b);cnt += right - left;}cout << cnt;return 0;
}

---

4. 煩惱的高考志愿 ??

【題目鏈接】

P1678 煩惱的高考志愿 - 洛谷

【題目背景】

計算機競賽小組的神牛 V 神終于結束了高考，然而作為班長的他還不能閑下來，班主任老 t 給了他一個艱巨的任務：幫同學找出最合理的大學填報方案。可是 v 神太忙了，身后還有一群小姑娘等著和他約會，于是他想到了同為計算機競賽小組的你，請你幫他完成這個艱巨的任務。

【題目描述】

現有 $m$ 所學校，每所學校預計分數線是 $a_i$。有 $n$ 位學生，估分分別為 $b_i$。

根據 $n$ 位學生的估分情況，分別給每位學生推薦一所學校，要求學校的預計分數線和學生的估分相差最小（可高可低，畢竟是估分嘛），這個最小值為不滿意度。求所有學生不滿意度和的最小值。

【輸入格式】

第一行讀入兩個整數 $m,n$。

第二行共有 $m$ 個數，表示 $m$ 個學校的預計錄取分數。

第三行有 $n$ 個數，表示 $n$ 個學生的估分成績。

【輸出格式】

輸出一行，為最小的不滿度之和。

【示例一】

輸入

4 3
513 598 567 689
500 600 550

輸出

32

【說明/提示】

數據范圍：

對于 $30\%$ 的數據，$1\le n,m\le 10^3$，估分和錄取線 $\le 10^4$；

對于 $100\%$ 的數據，$1\le n,m\le 10^5$，估分和錄取線 $\le 10^6$ 且均為非負整數。

---

(1) 解題思路

對于每一個學生的估分我們都需要找到與該分數 “最近” 的那個學校的分數，因此可以考慮排序 + 二分查找。

1. 創建兩個數組 sch[] 和 stu[] 分別存儲學校的分數線和學生的估分（下標從 1 開始）。
2. 先將學校的分數排序。
3. 對于每一個學生的估分 x，用二分查找找出大于等于 x 的最小的那個學校分數對應的下標 pos。
4. 設置一個變量 sum 記錄不滿意度的總和。根據二分查找，可以得出對于每一個估分 x，都有 sum += min(abs(x - stu[pos]), abs(x - stu[pos - 1]))。

對于上面的式子，做以下幾點說明：

• 如果找到的 pos 位于學校分數線數組的內部，那么顯然公式成立。
• 如果找到的 pos 位于 sch[] 數組的尾部，即所有學校的分數線都小于等于估分 x。那么一定有 abs(x - stu[pos]) < abs(x - stu[pos - 1])，顯然成立。
• 如果找到的 pos 位于 sch[] 數組的頭部（pos == 1），即可能出現所有分數線都高于估分 x 的情況，那么此時只能取 abs(x - stu[pos])。為了保證不取到 abs(x - stu[pos - 1])，我們需要讓 x - stu[0] 的值取絕對值是一個很大的數，這里的 stu[0] 可以稱它為 “左右護法”。

---

(2) 代碼實現

#include<iostream>
#include<algorithm>using namespace std;typedef long long LL;const int N = 1e5 + 10;
int sch[N], stu[N];
int m, n;// 查找大于等于 target 的最小元素的并返回其下標
int bisearch(int target)
{int left = 1, right = m;while (left < right){int mid = left + (right - left) / 2;if (sch[mid] < target) left = mid + 1;else right = mid;}return left;
}int main()
{cin >> m >> n;for (int i = 1; i <= m; i++) cin >> sch[i];for (int i = 1; i <= n; i++) cin >> stu[i];sort(sch + 1, sch + m + 1);sch[0] = -1e7;  // 加上左右護法LL sum = 0;for (int i = 1; i <= n; i++){int pos = bisearch(stu[i]);sum += min(abs(stu[i] - sch[pos]), abs(stu[i] - sch[pos - 1]));}cout << sum;return 0;
}

---

二、二分答案

1. 什么是二分答案

準確來說，應該是【二分答案 + 判斷】。

當一個問題的答案在某一個區間上都符合要求的時候，如果問這些符合要求的答案的最大值（最小值）時，我們往往可以采用二分答案去求解。

二分答案可以處理大部分【最大值最小】以及【最小值最大】的問題。如果一個問題的解空間在從小到大變化的過程中，判斷答案的結果出現二段性，此時我們就可以二分這個解空間，通過判斷，找出最優解。

---

2. 木材加工 ??

【題目鏈接】

P2440 木材加工 - 洛谷

【題目描述】

木材廠有 $n$ 根原木，現在想把這些木頭切割成 $k$ 段長度均為 $l$ 的小段木頭（木頭有可能有剩余）。

當然，我們希望得到的小段木頭越長越好，請求出 $l$ 的最大值。

木頭長度的單位是 $\text{cm}$，原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數。

例如有兩根原木長度分別為 $11$ 和 $21$，要求切割成等長的 $6$ 段，很明顯能切割出來的小段木頭長度最長為 $5$。

【輸入格式】

第一行是兩個正整數 $n,k$，分別表示原木的數量，需要得到的小段的數量。

接下來 $n$ 行，每行一個正整數 $L_i$，表示一根原木的長度。

【輸出格式】

僅一行，即 $l$ 的最大值。

如果連 $\text{1cm}$ 長的小段都切不出來，輸出 0。

【示例一】

輸入

3 7
232
124
456

輸出

114

【說明/提示】

對于 $100\%$ 的數據，有 $1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8(i\in [1,n])$。

---

(1) 解題思路

思路一：暴力解法

我們首先會想到暴力解法，即從小到大依次枚舉這個 l，看看如果分成長度為 l 能不能滿足要求，如果 l 足夠小，那么它就可以把木材分成很多段（段數 > k）從而符合要求，但是我們要的是最大的 l ，也就是說我們要不斷從小到大枚舉直到找到最后一個符合要求的 l 才是我們要的 l。

顯然，這會超時。

思路二：二分答案

通過觀察我們會發現，假設 l 的最大值我們記為 max_l，木材長度的最大值記為 max_len。那么在 [1, max_l] 的這段區間內都是能夠使切出的段數 >= k 的。而一旦在 (max_l, max_len] 這個范圍內就不符合要求了。也就是說這個 max_l 將問題的答案分成了兩段，一段符合要求，一段不符合要求，我們要找的就是符合要求的最大值。

接下來就可以采用二分答案來思考問題，既然這個問題的答案具有二段性，那么我們就沒必要一個一個枚舉 l 了，我們可以讓 left = 1, right = max_len，在這個區間內采用二分算法，如果 mid 指向的值（切割出的木材長度）符合要求，那么就讓 left 移動到 mid 的位置；否則讓 right 移動到 mid - 1 的位置，然后繼續二分去尋找答案。

---

(2) 代碼實現

#include<iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;
LL wood[N];
LL n, k;// 判斷如果切割為長度 x 能不能滿足題意 (段數 >= k)
bool check(LL x)
{LL c = 0;  // 記錄段數for(int i = 1; i <= n; i++){c += wood[i] / x;}return c >= k;
}int main()
{cin >> n >> k;LL max_len = 0;for(int i = 1; i <= n; i++){cin >> wood[i];max_len = max(max_len, wood[i]);}LL left = 1, right = max_len;// 二分while(left < right){LL mid = left + (right - left + 1) / 2;if(check(mid)) left = mid;  // 如果切割成長度 mid 能滿足條件else right = mid - 1;   // 否則}// 結束時記得判斷這個值是否符合條件，因為有可能 k 過大，導致怎么切都無法到 k 段，這時輸出 0if(check(left)) cout << left;else cout << 0;return 0;
}

---

3. 砍樹 ??

【題目鏈接】

[P1873 COCI 2011/2012 #5] EKO / 砍樹 - 洛谷

【題目描述】

伐木工人 Mirko 需要砍 $M$ 米長的木材。對 Mirko 來說這是很簡單的工作，因為他有一個漂亮的新伐木機，可以如野火一般砍伐森林。不過，Mirko 只被允許砍伐一排樹。

Mirko 的伐木機工作流程如下：Mirko 設置一個高度參數 $H$（米），伐木機升起一個巨大的鋸片到高度 $H$，并鋸掉所有樹比 $H$ 高的部分（當然，樹木不高于 $H$ 米的部分保持不變）。Mirko 就得到樹木被鋸下的部分。例如，如果一排樹的高度分別為 $20,15,10$ 和 $17$，Mirko 把鋸片升到 $15$ 米的高度，切割后樹木剩下的高度將是 $15,15,10$ 和 $15$，而 Mirko 將從第 $1$ 棵樹得到 $5$ 米，從第 $4$ 棵樹得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常關注生態保護，所以他不會砍掉過多的木材。這也是他盡可能高地設定伐木機鋸片的原因。請幫助 Mirko 找到伐木機鋸片的最大的整數高度 $H$，使得他能得到的木材至少為 $M$ 米。換句話說，如果再升高 $1$ 米，他將得不到 $M$ 米木材。

【輸入格式】

第 $1$ 行 $2$ 個整數 $N$ 和 $M$，$N$ 表示樹木的數量，$M$ 表示需要的木材總長度。

第 $2$ 行 $N$ 個整數表示每棵樹的高度。

【輸出格式】

$1$ 個整數，表示鋸片的最高高度。

【示例一】

輸入

4 7
20 15 10 17

輸出

15

【示例二】

輸入

5 20
4 42 40 26 46

輸出

36

【說明/提示】

對于 $100\%$ 的測試數據，$1\le N\le 10^6$，$1\le M\le 2\times 10^9$，樹的高度 $\le 4\times 10^5$，所有樹的高度總和 $>M$。

---

(1) 解題思路

和上一道題十分類似，我們會發現，假設最高高度記為 max_h，那么當鋸片高度為 [0, max_h] 時我們都能獲得 >= M 米的木材，而一旦高度大于 max_h，我們將無法獲得那么多木材。因此，為了找到這個最高高度 max_h，可以采用二分來尋找。

---

(2) 代碼實現

#include<iostream>using namespace std;typedef long long LL;const int N = 1e6 + 10;
LL tree[N];
LL n, m;// 如果鋸片的高度為 h，檢查其能否得到 >= M 米的木材
bool check(int h)
{LL sum = 0;  // 能收獲的木材總長度for(int i = 1; i <= n; i++){if(tree[i] > h) sum += tree[i] - h;}return sum >= m;
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++) cin >> tree[i];// 在[0, 1e5]區間內二分，尋找符合條件的高度int left = 0, right = 4e5;while(left < right){int mid = left + (right - left + 1) / 2;if(check(mid)) left = mid;  // 如果 mid 高度時能符合條件else right = mid - 1;  // 否則 }cout << left;return 0;
}

---

4. 跳石頭 ??

【題目鏈接】

[P2678 NOIP 2015 提高組] 跳石頭 - 洛谷

【題目描述】

一年一度的“跳石頭”比賽又要開始了！

這項比賽將在一條筆直的河道中進行，河道中分布著一些巨大巖石。組委會已經選擇好了兩塊巖石作為比賽起點和終點。在起點和終點之間，有 $N$ 塊巖石（不含起點和終點的巖石）。在比賽過程中，選手們將從起點出發，每一步跳向相鄰的巖石，直至到達終點。

為了提高比賽難度，組委會計劃移走一些巖石，使得選手們在比賽過程中的最短跳躍距離盡可能長。由于預算限制，組委會至多從起點和終點之間移走 $M$ 塊巖石（不能移走起點和終點的巖石）。

【輸入格式】

第一行包含三個整數 $L,N,M$，分別表示起點到終點的距離，起點和終點之間的巖石數，以及組委會至多移走的巖石數。保證 $L\ge 1$ 且 $N\ge M\ge 0$。

接下來 $N$ 行，每行一個整數，第 $i$ 行的整數 $D_i(0<D_i<L)$， 表示第 $i$ 塊巖石與起點的距離。這些巖石按與起點距離從小到大的順序給出，且不會有兩個巖石出現在同一個位置。

【輸出格式】

一個整數，即最短跳躍距離的最大值。

【示例一】

輸入

25 5 2 
2
11
14
17 
21

輸出

4

【說明/提示】

輸入輸出樣例 1 說明

將與起點距離為 $2$ 和 $14$ 的兩個巖石移走后，最短的跳躍距離為 $4$（從與起點距離 $17$ 的巖石跳到距離 $21$ 的巖石，或者從距離 $21$ 的巖石跳到終點）。

數據規模與約定

對于 $20\%$的數據，$0\le M\le N\le 10$。
對于 $50\%$ 的數據，$0\le M\le N\le 100$。
對于 $100\%$ 的數據，$0\le M\le N\le 50000,1\le L\le 10^9$。

---

(1) 解題思路

我們需要求得的是最短的跳躍距離的最大值，不難發現，當最短跳躍距離越大時，我們需要移走的石頭數目就越多。也就是說，如果我們把這個最短跳躍距離的最大值設為 max_d 的話，那么在 [0, max_d] 范圍內，我們需要移走的石頭都是小于能移走的石頭數目 M 的，而一旦超出了這個 max_d，那么我們就無法移走那么多石頭，不符合題意。因此為了找到這個 max_d，我們可以利用二分去尋找。用二分去枚舉最短跳躍距離 x，檢查這個最短跳躍距離對應所需要移走的數目是否小于等于 M。

• 如何計算出對于每一個最短跳躍距離 x，需要移走的石頭數目？

1. 定義前后兩個指針 i 和 j 遍歷整個數組，設 i <= j，每次 j 從 i 的位置往后移動；

2. 當發現 a[j] - a[i] >= x 時，說明 [i + 1, j - 1] 之間的石頭都可以移走；

3. 然后將 i 更新到 j 的位置，繼續重復 1、2 兩步。

---

(2) 代碼實現

#include<iostream>using namespace std;typedef long long LL;const int N = 5e4 + 10;
LL dist[N];
LL l, n, m;// 檢查如果最短跳躍距離為 x 時，需要移走的巖石數是否 <= M
bool check(LL x)
{LL cnt = 0;  // 記錄移走的巖石數for(int i = 0; i <= n; i++){int j = i + 1;while(j <= n && dist[j] - dist[i] < x) j++;cnt += j - i - 1;i = j - 1;}return cnt <= m;
}int main()
{cin >> l >> n >> m;for(int i = 1; i <= n; i++) cin >> dist[i];dist[n + 1] = l;  // 最后一個巖石的距離（終點）n++;  // 注意添加了最后一個巖石的距離之后要把 n 加上一LL left = 0, right = l;while(left < right){LL mid = left + (right - left + 1) / 2;if(check(mid)) left = mid;else right = mid - 1;}cout << left;return 0;
}