---
# System prepended metadata

title: 【C++】競程筆記：二分搜考題總整理
tags: [C++, 競程, 演算法, CP, 二分搜]

---

# 【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;
    }
};
```