【C++】競程筆記：二分搜考題總整理

二分搜寫法模板

  • 模板一（找精確值）： 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/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 就是元素的插入位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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/

原始人寫法（不推）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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。

1
2
3
4
5
6
7
8
9
10
11
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/

格式長這樣：

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

前面沒啥問題，就是二分搜的基本形式。

後面需要注意，該題要判斷哪一半是有序的，如果 nums[mid] >= nums[left]，代表 [left, mid] 這一段是有序遞增的；反之代表右半邊 [mid, right] 是有序遞增的。

這兩個判斷都要再巢狀判斷檢查 target 是否夾在左或右半邊這個有序區間內。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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--，逐步排除重複項。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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：

1
2
3
4
5
6
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）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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/

這題也是…：

1
2
3
4
5
6
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        return distance(nums.begin(), max_element(nums.begin(), nums.end()));
    }
};

二分搜解法，實際上跟上題的思路幾乎一樣：

但這邊解法就有點像微分求切線斜率的概念，如果遇到上坡（nums[mid] < nums[mid+1]），那麼就往右走，反之遇到下坡就往左縮，或可能目前位置就是題目要求的峰值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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) 也行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 必須放到隔天（下一艘船）去載。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
求最小載重求最小化的最大和

程式碼完全照抄，稍微改一下變數即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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]$ ，縮小範圍到右半邊。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
};