# 【C++】競程筆記：二分搜考題總整理
[TOC]
## 二分搜寫法模板
* 模板一（找精確值）： `while (left <= right)`，迴圈結束後 `left > right`。
* 模板二（找邊界/答案）： `while (left < right)`，通常配合 `right = mid` 或 `left = mid + 1`，結束時 `left == right`。
## 索引搜尋（Index Search）
### 標準搜尋入門題（704. Binary Search）
Problem Source：https://leetcode.com/problems/binary-search/
```cpp=
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
};
```
### 插入位置型（35. Search Insert Position）
Problem Source：https://leetcode.com/problems/search-insert-position/
這種寫法為第一種模板，結束後會得到 `left > right`，此時回傳 `left` 就是元素的插入位置。
```cpp=
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target){
return mid;
}
else if (nums[mid] > target){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return left;
}
};
```
### 必考：尋找邊界型（34. Find First and Last Position of Element in Sorted Array）
Problem Source：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
原始人寫法（不推）：
```cpp=
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int first = findBound(nums, target, true);
if (first == -1) return {-1, -1};
int last = findBound(nums, target, false);
return {first, last};
}
private:
int findBound(vector<int>&nums, int target, bool isFirst){
int left = 0, right = nums.size() - 1;
int ans = -1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target){
ans = mid;
if (isFirst) right = mid - 1;
else left = mid + 1;
}
else if (nums[mid] < target){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return ans;
}
};
```
STL 懶人寫法：
First 就是 `lower_bound()`，Last 就是 `upper_bound()`。
用 `distance(v.begin(), lower/upper)` 算 index，`upper_bound()` 記得 - 1。
```cpp=
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
auto lower = lower_bound(nums.begin(), nums.end(), target);
auto upper = upper_bound(nums.begin(), nums.end(), target);
if (lower == nums.end() || *lower != target){
return {-1, -1};
}
return {(int)distance(nums.begin(), lower), (int)distance(nums.begin(), upper - 1)};
}
};
```
## 變體與旋轉陣列（Modified Array）
該類題目 array 並非完全排序，但有局部排序或特定規律的特性，仍可用二分搜把搜尋區間減半。
不需要全部排序，只需判斷目標在哪一半。
### 旋轉搜尋（33. Search in Rotated Sorted Array）
Problem Source：https://leetcode.com/problems/search-in-rotated-sorted-array/description/
格式長這樣：
```
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
```
前面沒啥問題，就是二分搜的基本形式。
後面需要注意，該題要判斷哪一半是有序的，如果 `nums[mid] >= nums[left]`，代表 `[left, mid]` 這一段是有序遞增的；反之代表右半邊 `[mid, right]` 是有序遞增的。
這兩個判斷都要再巢狀判斷檢查 target 是否夾在左或右半邊這個有序區間內。
```cpp=
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] >= nums[left]){
if (target >= nums[left] && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if (target > nums[mid] && target <= nums[right])
left = mid + 1;
else{
right = mid - 1;
}
}
}
return -1;
}
};
```
### 旋轉含重複（81. Search in Rotated Sorted Array II）
前一題的 Plus 版本。
Problem Source：https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/
解題邏輯與上題差不多，但有個問題，就是如果 `nums[left] == nums[mid]` 且 `nums[mid] == nums[right]`，那就沒有辦法判斷了。
解法就是同時縮減邊界 `left++` 和 `right--`，逐步排除重複項。
```cpp=
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
continue;
}
if (nums[mid] >= nums[left]){
if (target >= nums[left] && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if (target > nums[mid] && target <= nums[right])
left = mid + 1;
else{
right = mid - 1;
}
}
}
return false;
}
};
```
### 尋找極值（153. Find Minimum in Rotated Sorted Array）
Problem Source：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
嗯...這題只要用黑魔法就好了XD：
```cpp=
class Solution {
public:
int findMin(vector<int>& nums) {
return *min_element(nums.begin(), nums.end());
}
};
```
但還是要做二分搜啦，以下是解法：
在這邊用 `left < right` 模板，而非 `left <= right`，因為是在縮小區間找一個具體位置。
然後有兩種情況：
* `if (nums[mid] > nums[right])` 中間值比較大，代表最小值一定在右半邊。
* `else` 中間值小於等於右邊，代表右半邊是有序的，最小值在左半邊（含 mid）。
```cpp=
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right){
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]){
left = mid + 1;
}
else{
right = mid;
}
}
return nums[left];
}
};
```
### 尋找峰值（162. Find Peak Element）
Problem Source：https://leetcode.com/problems/find-peak-element/description/
這題也是...：
```cpp=
class Solution {
public:
int findPeakElement(vector<int>& nums) {
return distance(nums.begin(), max_element(nums.begin(), nums.end()));
}
};
```
二分搜解法，實際上跟上題的思路幾乎一樣：
但這邊解法就有點像微分求切線斜率的概念，如果遇到上坡（`nums[mid] < nums[mid+1]`），那麼就往右走，反之遇到下坡就往左縮，或可能目前位置就是題目要求的峰值。
```cpp=
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right){
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]){
left = mid + 1;
}
else{
right = mid;
}
}
return left;
}
};
```
## 對答案二分搜（Binary Search on Answer）
這種題型的二分搜是最難的，很多題目甚至靠這鬼東西噁心你。
題目通常不會給你一個明確的陣列，而是求一個最小的 x 或最大的 y 滿足特定條件。
通常解題思路是這三種：
* 解空間單調性。如果答案 $k$ 可行，那 $k+1$ 通常也可行（或反之）。
* 將最佳化問題轉化為判定問題。
* 通常配合 `check(mid)` 函數來驗證 $mid$ 是否符合題意。
判斷是不是對答案二分搜的徵兆：
* 題目出現最大化最小值或最小化最大值。
* 輸入範圍很大（如 $10^9$），無法用 DP 或暴力解，但答案本身有範圍。
### 數學（69. Sqrt(x)）
Problem Source：https://leetcode.com/problems/sqrtx/description/
先判定 base case，x = 0, x = 1 的情況，之後再做二分搜。
由於題目給的範圍有到 $2^31 - 1$ ，所以 $mid \times mid$ 必定會超過 int 的範圍，導致 overflow，因此強制轉型成 long long。
至於為何是回傳 right？因為迴圈結束條件是 left > right，right 一定比較小。舉個例子， $x = 8$ 的輸出是 $2.82842\cdots$ ，題目只取 2。
```cpp=
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
if (x == 1) return 1;
int left = 1, right = x;
while (left <= right){
int mid = left + (right - left) / 2;
if ((long long)mid * mid == x){
return mid;
}
else if ((long long)mid * mid < x){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return right;
}
};
```
### 速度/速率（875. Koko Eating Bananas）
Problem Source：https://leetcode.com/problems/koko-eating-bananas/description/
這題就是最典型的對答案二分搜題型了。
不要把平常找數字的概念套進去這題裡面，而是要在 $1$ 到 $max(piles)$ 這個速度區間內找一個最小的可行速度。
解題思路：
1. 定義搜尋區間
- 最小值 L 為 1，因為最慢一小時只能吃一根。
- 最大值 R 為 $max(piles)$
2. 二分搜
- 取中間速度 `mid = L + (R - L) / 2`。
- 計算以 `mid` 速度吃完所有香蕉需要幾小時（變數 `hoursNeeded`）。
- 判斷式：
- 如果 `hoursNeeded <= h`：代表時間還行，要再慢一點（縮小右邊界 right = mid）。
- 如果 `hoursNeeded > h`：代表超時，要快點（縮小左邊界 left = mid + 1）。
因為速度可以任意調，而題目有限制 h 最大是 $10^9$ ，所以可以合理將 right 設定為題目範圍最大值。
`hourSpent += (pile + speed - 1) / speed;` 在做無條件進位，因為這題是有關於時間的，像是一堆裡面有 7 根香蕉，而速度是一小時吃 3 根，吃完要吃 3 小時。
或寫 `hourSpent += ceil((double)a / b)` 也行。
```cpp=
class Solution {
public:
bool check(const vector<int>& piles, int h, int speed){
long long hourSpent = 0;
for (int pile : piles){
hourSpent += (pile + speed - 1) / speed;
}
return hourSpent <= h;
}
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1, right = 1000000000;
while (left < right){
int mid = left + (right - left) / 2;
if (check(piles, h, mid)){
right = mid;
}
else{
left = mid + 1;
}
}
return left;
}
};
```
### 容量限制（1011. Capacity To Ship Packages Within D Days）
Problem Source：https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/
基本上這題跟前面那題是差不多寫法的，只是在 left 跟 right 的設定上需要多加注意。
left 的設定是 `max(weights)`，因為船的載重至少要載得動船上最重的物品，不然不能在 D 天內全部載走。
right 為 `sum(weights)`，假設 edge case 是給你 1 天時間載走所有的 packages，那麼這個船的載重就必須是所有物品的重量和。
`dayNeeded` 變數是從第一天開始，故預設值為 1。接下來 `check()` 的演算流程就是屬於貪心法的部分了。
按照 packages 順序依序裝船。
如果 `currLoad + w <= capacity` 則裝運上船，其中 w 是下一個 package。
如果 `currLoad + w > capacity` 就超重了，表示這艘船就必須要出發了（`dayNeeded++`），下一個 package 必須放到隔天（下一艘船）去載。
```cpp=
class Solution {
public:
bool check(const vector<int>& weights, int days, int capacity){
int dayNeeded = 1;
int currLoad = 0;
for (int w : weights){
if (currLoad + w > capacity){
dayNeeded++;
currLoad = 0;
}
currLoad += w;
}
return dayNeeded <= days;
}
int shipWithinDays(vector<int>& weights, int days) {
int left = *max_element(weights.begin(), weights.end()), right = accumulate(weights.begin(), weights.end(), 0);
while (left < right){
int mid = left + (right - left) / 2;
if (check(weights, days, mid)){
right = mid;
}
else{
left = mid + 1;
}
}
return left;
}
};
```
### 資源分配（410. Split Array Largest Sum）
Problem Source：https://leetcode.com/problems/split-array-largest-sum/description/
題目要求的是將陣列切成 $k$ 份，讓這 $k$ 份中總和最大的那一份，數值盡可能小。
這題雖然是 Hard，但稍微對照一下上一題就會發現有所端倪。
| 1011 運貨題 | 本題 |
| -------- | -------- |
| 每天送 package | 每個子陣列 |
| 限制天數 D | 限制切成 k 份 |
| 船的載重量 Capacity | 子陣列的最大和 Largest Sum |
| 求最小載重 | 求最小化的最大和 |
程式碼完全照抄，稍微改一下變數即可。
```cpp=
class Solution {
public:
int check(vector<int>&nums, int k, int limit){
int cut = 1;
int currSum = 0;
for (int num : nums){
if (currSum + num > limit){
cut++;
currSum = 0;
}
currSum += num;
}
return cut <= k;
}
int splitArray(vector<int>& nums, int k) {
int left = *max_element(nums.begin(), nums.end()), right = accumulate(nums.begin(), nums.end(), 0);
while (left < right){
int mid = left + (right - left) / 2;
if (check(nums, k, mid)){
right = mid;
}
else{
left = mid + 1;
}
}
return left;
}
};
```
### 287. Find the Duplicate Number
Problem Source：https://leetcode.com/problems/find-the-duplicate-number/description/
這題看似是找重複數字的 hash table 類型題目，但題目限制不能直接動陣列，而且只能用 $O(1)$ 額外空間，所以標準解法為對數值範圍進行二分搜。
這題也應用到一個數學原理叫做鴿籠原理（Pigeonhole Principle），請見 https://www-math.nsysu.edu.tw/highschool/20151226.pdf
題目數字範圍是 $[1, n]$，陣列長度是 $n+1$。所以至少一定有一個數字是重複的。
然後注意不是對 index 做二分搜，而是數值範圍 $[1, n]$ 做二分搜。
Check 邏輯（鴿籠原理）：
設選一個中間值 mid，遍歷整個陣列，計算 <= mid 的數字有幾個（記為 count）。
- 如果沒有重複數字：在 $[1, mid]$ 範圍內的數字最多應該只有 mid 個（如 $1 \sim 4$ 應僅 4 個）。
- 如果 $count > mid$ ：根據鴿籠原理，表示在 $[1, mid]$ 這個區間內，塞了太多數字，重複的數字一定落在這個區間內，縮小範圍到左半邊。
- 如果 $count <= mid$ ：代表左半邊 $[1, mid]$ 沒問題，重複的情況發生在右半邊 $[mid+1, n]$ ，縮小範圍到右半邊。
```cpp=
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1, right = nums.size() - 1;
while (left < right){
int mid = left + (right - left) / 2;
int count = 0;
for (int num : nums){
if (num <= mid) count++;
}
if (count > mid){
right = mid;
}
else{
left = mid + 1;
}
}
return left;
}
};
```
Sign in with Wallet
Connect another wallet